전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
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 s in string :
if s not in curr_node.children :
curr_node.children[s] = Node(s)
curr_node = curr_node.children[s]
curr_node.data = string
def search_prefix(self, string) :
curr_node = self.head
for s in string :
curr_node = curr_node.children[s]
if curr_node.children :
return False
else :
return True
t = int(input())
for _ in range(t) :
n = int(input())
trie =Trie()
nums = []
for _ in range(n) :
num = input().rstrip()
nums.append(num)
trie.insert(num)
flag = True
nums.sort()
for num in nums :
if not trie.search_prefix(num) :
flag = False
break
if flag :
print('YES')
else :
print('NO')
T = int(input())
for t in range(T) :
#전화번호수
n = int(input())
lst = []
#전화번호 넣어주기
for i in range(n) :
x = input()
lst.append(x)
#정렬
lst.sort()
#초기정답 yes
res = 'YES'
#내 전화번호가 다음전화번호의 접두어인지 확인
for i in range(n-1) :
if lst[i] == lst[i+1][:len(lst[i])] :
res = 'NO'
print(res)
break
else :
print(res)