[BOJ_Gold 4] 5052 - 전화번호 목록 [python]

5052번: 전화번호 목록 (acmicpc.net)

5052번: 전화번호 목록

문제

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

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

============================================================================

 

간단한 Trie 구현 문제입니다.

각 테스트 케이스 별로 Trie를 구현하고, 입력으로 들어오는 전화번호에 따라 자식 노드를 만들어가며 순회합니다.

마지막 값이 들어가는 노드에는 end값을 True로 설정해줍니다.

 

이후 다른 값이 들어왔을 때, 해당 위치가 마지막 값이면서 기존에 만들어진 노드로 들어왔다면,

혹은 현재 위치가 이전에 들어왔던 어떤 값의 마지막 위치라면, 해당 전화번호 목록은 일관성을 잃게됩니다.

때문에, Input함수를 통해 상술한 두 상황에서 1을 리턴한다면, 우리는 전화번호 목록의 일관성을 알 수 있습니다.

 

가령 다음과 같은 상황에서, 01이 입력되며 입력값의 마지막인 1의 End가 True가 된 상황에서 010값을 넣기 위해 진행한다면, 진행 도중 End가 True인 1을 만나 1을 리턴하게됩니다.

 

이와 반대로, 010이 이미 입력된 상황에서 01이 들어온다면, 입력의 끝인 1이 이미 있던 노드였기 때문에 마찬가지로 1를 리턴하게 됩니다.

import sys
from collections import deque

class TrieNode():
    def __init__(self):
        self.child = dict()
        self.end = False

    def Input(self,valueQueue):
        cur = self
        while valueQueue:
            v = valueQueue.popleft()
            if v not in cur.child:
                cur.child[v] = TrieNode()
            elif not queue or cur.child[v].end: return 1

            cur = cur.child[v]
        cur.end = True
        return 0

input = sys.stdin.readline

for i in range(int(input())):
    Trie = TrieNode()
    flg = True
    for j in range(int(input())):
        value = list(input().rstrip())
        if flg:
            queue = deque()
            for v in value:
                queue.append(v)

            if Trie.Input(queue):
                flg = False

    print("YES" if flg else "NO")