[프로그래머스] 전화번호 목록

기본 아이디어

• 트라이 노드
• 순서 정렬 or 양방향 접두사 여부 체크

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, number):
        node = self.root
        for n in number:
            if n not in node.children:
                node.children[n] = TrieNode()
            node = node.children[n]
        node.is_end = True

    def search(self, number):
        node = self.root
        for n in number:
            if n not in node.children:
                if node.is_end:
                    return True   # 기존 단어가 number의 접두사인 경우
                return False
            node = node.children[n]
        return True   # number가 기존 단어의 접두사인 경우

def solution(phone_book):
    trie = Trie()
    trie.insert(phone_book[0])
    for number in phone_book[1:]:
        if trie.search(number):
            return False
        else:
            trie.insert(number)
    return True

• search 함수 쪽에 양방향으로 접두사를 체크해줄 수 있도록 구현함 (리스트를 길이순으로 정렬해서 넣어주면 시간초과입니다~!)