[BOJ] [Python] 5052 : 전화번호 목록

하나라도 문자열 전체가, 다른 문자열과 겹친다면 NO를 출력한다. (아니면 YES.)

트라이를 이용해서 해결했다.

 

주의해야 할 점은 '911', '91125426'과 같은 입력이 같이 들어올 때이다.

 

1. '91125426'이 먼저 들어오고 그 후에 '911'이 들어온다.

search 함수에서, '911'이 트라이를 돌면서 문자열 전체가 겹친다면 True를 반환한다. 

 

2. '911'이 먼저 들어오고 그 후에 '91125426'이 들어온다.

search 함수에서, '91125426'이 트라이를 돌면서 data가 None이 아니라면 어떤 문자열과 겹치는 것이다.

True를 반환한다.

 

1, 2가 모두 해당이 안 된다면 insert 함수를 실행시켜, 문자열을 트라이에 넣어준다. 

 

 

import sys


class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}


class Trie(object):
    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        curr_node = self.head

        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
        curr_node.data = string

    def search(self, string):
        curr_node = self.head

        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]

                if curr_node.data is not None:
                    return True  # 91125426 -> 911
            else:
                return t.insert(string)  # insert

        return True  # 911 -> 91125426


for _ in range(int(input())):
    t = Trie()
    boolean = True

    for _ in range(int(input())):
        number = sys.stdin.readline().rstrip()

        if not boolean:
            continue

        if t.search(number):
            print("NO")
            boolean = False

    if boolean:
        print("YES")

 

 

처음에는, "NO"가 출력되는 순간 그 케이스는 더 볼 필요가 없다고 생각했다.

하지만 이는 반만 맞는 말이다.

 

"NO"가 출력되면 해당 케이스의 나머지 예시를 따질 필요가 없다. 하지만 입력은 받아야 한다.

이를 간과해서 런타임 에러 (EOFError)가 나왔다.

 

continue를 이용해서 입력만 받도록 수정했다.