Baekjoon 5052
in Study / Computer science on Baekjoon 5052
Sort, Tree, Trie
Description
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
긴급전화: 911
상근: 97 625 999
선영: 91 12 54 26
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
Input
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
Output
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
Example I & O
Input
2
3
911
97625999
91125426
5
113
12340
123440
12345
98346
Output
NO
YES
My solution
import sys
input = sys.stdin.readline
class Node(object):
def __init__(self, key, data = None):
self.key = key
self.data = data
self.child = {}
class Trie(object):
def __init__(self):
self.head = Node(None)
def insert_true(self, string):
current_node = self.head
for c in string:
if current_node.data:
return False
if c not in current_node.child:
current_node.child[c] = Node(c)
current_node = current_node.child[c]
current_node.data = string
return True
def quick_sort(array):
if len(array) <= 1:
return array
pivot = len(array) // 2
front_arr, pivot_arr, back_arr = [], [], []
for value in array:
if len(value) < len(array[pivot]):
front_arr.append(value)
elif len(value) > len(array[pivot]):
back_arr.append(value)
else:
pivot_arr.append(value)
if len(front_arr) == 0 and len(back_arr) == 0 and len(pivot_arr) != 0:
return pivot_arr
return quick_sort(front_arr) + quick_sort(pivot_arr) + quick_sort(back_arr)
t = int(input())
result = []
for i in range(t):
n = int(input())
phone_list = []
for j in range(n):
num = input()
phone_list.append(num[:-1])
phone_list = quick_sort(phone_list)
phone_trie = Trie()
flag = True
for number in phone_list:
if phone_trie.insert_true(number):
continue
else:
result.append("NO")
flag = False
break
if flag:
result.append("YES")
for i in result:
print(i)
- Sketch
While dealing with inserting issue: If current_node has data (If current_node was for last char from a certain string), the output should be “NO”
For this, short string should be saved into trie as quickly as possible : sort algorithm is needed
- Code Analysis
class Trie(object):
def __init__(self):
self.head = Node(None)
def insert_true(self, string):
current_node = self.head
for c in string:
if current_node.data:
return False
if c not in current_node.child:
current_node.child[c] = Node(c)
current_node = current_node.child[c]
current_node.data = string
return True
insert_true : current_node has data → return False // otherwise → return True
def quick_sort(array):
if len(array) <= 1:
return array
pivot = len(array) // 2
front_arr, pivot_arr, back_arr = [], [], []
for value in array:
if len(value) < len(array[pivot]):
front_arr.append(value)
elif len(value) > len(array[pivot]):
back_arr.append(value)
else:
pivot_arr.append(value)
if len(front_arr) == 0 and len(back_arr) == 0 and len(pivot_arr) != 0:
return pivot_arr
return quick_sort(front_arr) + quick_sort(pivot_arr) + quick_sort(back_arr)
quick sort based on the length of string
t = int(input())
result = []
for i in range(t):
n = int(input())
phone_list = []
for j in range(n):
num = input()
phone_list.append(num[:-1])
result : outputs from the test cases
num : If 911 was input, num == “911\n”
\n should be removed
phone_list = quick_sort(phone_list)
phone_trie = Trie()
flag = True
for number in phone_list:
if phone_trie.insert_true(number):
continue
else:
result.append("NO")
flag = False
break
if flag:
result.append("YES")
phone_list should be sorted based on the length of string
insert_true returns False : “NO” gonna be saved into result directly