전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
긴급전화: 911
상근: 97 625 999
선영: 91 12 54 26
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
import sys
class Node:
def __init__(self, key):
self.key = key
self.data = None
self.children = dict()
class Trie:
def __init__(self):
self.root = Node(None)
def insert(self, string: str):
current = self.root
for char in string:
if char not in current.children:
current.children[char] = Node(char)
current = current.children[char]
# 문자열의 끝을 알리기 위함.
current.data = string
# 문자열이 존재하는지만 파악
def search(self, string: str) -> bool:
current = self.root
for char in string:
if char not in current.children:
return False
current = current.children[char]
return current.data == string
def starts_with(self, prefix: str) -> bool:
current = self.root
for char in prefix:
if char not in current.children:
return False
current = current.children[char]
# 더 이상 자식 노드가 없으면, 파라미터 prefix로 겹치는 문자열은 없음.
# 반면에 있을 경우에는 반드시 prefix와 겹치는 문자열이 있다는 뜻.
return len(current.children) > 0
test_case = int(sys.stdin.readline().rstrip())
answer = []
for _ in range(test_case):
n = int(sys.stdin.readline().rstrip())
trie = Trie()
phone_numbers = []
for i in range(n):
data = sys.stdin.readline().rstrip()
phone_numbers.append(data)
trie.insert(data)
is_consistent = True
for i in range(n):
if trie.starts_with(phone_numbers[i]):
is_consistent = False
break
if is_consistent:
answer.append("YES")
else:
answer.append("NO")
for elem in answer:
print(elem)
전화 번호를 문자열
이라 취급할 수 있고, 문제에서 접두어
란 키워드가 존재한다. 접두어
와 관련이 있고, 빠르게 문자열
을 탐색할 수 있는 자료구조는 트라이
다.