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

문제 보기

이 문제는 해쉬 문제이다. 그런데 접두사라는 특징이 보여서 지금까지 한 번도 해본 적 없는 트라이로 풀어보았다.

문제를 푼 로직은 다음과 같다.

 

1. 전화번호부에 있는 전화번호들을 정렬한다. (26번째 줄)
2. 정렬이 끝나면 길이가 짧은 문자열부터 차례대로 나열되는데, 이 때 트라이에 삽입하면서 확장시켜나간다.
   트라이에 삽입할 때, 문자열의 마지막 노드에 end라는 불리언 변수를 True로 설정한다. (21번째 줄)
   만약 어떤 문자열을 트라이에 삽입할 때, end가 True인 노드를 만난다면 이전에 같은 문자열이 삽입되었다는 뜻이므로 False를 반환한다. (18~20번째, 29~30번째 줄)

 

class Node(object):
    def __init__(self, value, end=False):
        self.value = value
        self.children = dict()
        self.end = end
 
 
class Trie(object):
    def __init__(self):
        self.root = Node(None)
        
    def insert(self, string):
        cur = self.root
        for c in string:
            if c not in cur.children:
                cur.children[c] = Node(c)
            cur = cur.children[c]
            # if this is the end of the string
            if cur.end:
                return False
        cur.end = True
        return True
        
 
def solution(phone_book):
    phone_book.sort()
    trie = Trie()
    for phone_number in phone_book:
        if not trie.insert(phone_number):
            return False
    return True