[백준] (5052) 전화번호 목록 [Python]

문제 링크

https://www.acmicpc.net/problem/5052

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

• 입력 : 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
• 출력 : 각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

---

코드

class Node:
    def __init__(self, value, parent):
        self.value = value
        self.parent = parent
        self.child = dict()
        self.is_leaf = False
    def add_child(self, key, child):
        self.child[key] = child
    def find_child(self, key):
        return self.child.get(key)

t = int(input())
for _ in range(t):
    n = int(input())
    root = Node('', None)
    flag = True
    arr = list()
    for _ in range(n):
        arr.append(input())
    arr.sort(key=lambda x: (x, -len(x)))
    for s in arr:
        cur = root
        for i in range(len(s)):
            ch = cur.find_child(s[i])
            if not ch:
                ch = Node(s[i], cur)
            if cur.is_leaf:
                flag = False
                break
            cur.add_child(s[i], ch)
            cur = ch
        if not flag:
            break
        cur.is_leaf = True
    print("YES" if flag else "NO")

해설

기존 코드에서는 Trie 노드의 자식 노드를 리스트 형태로 관리했다. 이 리스트는 특정 문자에 해당하는 자식 노드를 찾기 위해 O(k)의 시간 복잡도로 리스트 전체를 순차적으로 탐색하는 비효율적인 문제를 안고 있었다. 같은 문자에 해당하는 노드가 리스트에 중복 저장될 가능성까지 있어 k값이 불필요하게 커지는 문제점도 있었다.

 

이러한 문제를 해결하기 위해, 자식 노드 관리 방식을 해시 맵의 특성을 가진 dictionary로 변경했다. 딕셔너리는 키를 통해 값을 평균 O(1)의 시간 복잡도로 빠르게 찾고 접근할 수 있는 특성을 가졌다. 이처럼 빠른 탐색 속도를 활용해, 기존의 O(k) 탐색 문제를 평균 O(1)로 개선하여 전체 알고리즘의 실행 시간을 크게 단축했다.