kangspa.com
출처 : 전화번호 목록
Solution
Python
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(self, lst):
# 현재 노드 위치 가리키는 now
now = self.head
# 문자 하나씩 key로 잡고, 노드를 만들어서 내려감
for c in lst:
if c not in now.child:
now.child[c] = Node(c)
now = now.child[c]
# lst의 모든 문자를 key로 해서 노드가 만들어졌으면, 마지막 노드에 data 추가
now.data = lst
def search(self, lst):
# 현재 노드 위치 가리키는 now
now = self.head
# 만들어둔 트라이 구조에서 lst를 끝까지 검색
for c in lst:
now = now.child[c]
# 검색 결과 하위 노드가 있다면(접두어라면) False
if now.child: return False
# 없다면 True
else: return True
if __name__ == '__main__':
t = int(input())
for _ in range(t):
n = int(input())
# 예제 1번 보면 공백은 없애는게 맞음
phone = [input().strip().replace(' ', '') for _ in range(n)]
# 각 TC에 대해 트라이 구조 생성
trie = Trie()
# 각 번호들을 트라이 구조에 입력
for lst in phone: trie.insert(lst)
# 유효한 목록인지 체크할 변수 flag
flag = True
# 각 번호를 검색하며, 한번이라도 유효하지 않으면 False로 변환
for lst in phone:
if not trie.search(lst):
flag = False
break
# 유효하면 YES, 유효하지 않으면 NO
if flag: print('YES')
else: print('NO')
'''
# sort하면 사전순 우선 정렬 후 길이 짧은 것부터 정렬되는 특성 활용
def valid(lst):
# 이미 정렬됐으니까, 목록에서 i-1이 i의 접두어인지만 확인하면 됨.
for i in range(1, len(lst)):
# 목록에서 앞 번호 길이가 뒷 번호 길이 이상이라면, 접두어가 아니니 패스
n, m = len(lst[i-1]), len(lst[i])
if n >= m: continue
# i에서 n까지의 번호가 i-1의 접두어인지 체크
if lst[i-1]==lst[i][:n]: return False
return True
if __name__ == '__main__':
t = int(input())
for _ in range(t):
n = int(input())
# 예제 1번 보면 공백은 없애는게 맞음
phone = [input().strip().replace(' ', '') for _ in range(n)]
# 우선 정렬
phone.sort()
# 유효한 목록이면, YES / 아니면 NO
if valid(phone): print('YES')
else: print('NO')
'''
문제
전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.
전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.
예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자
- 긴급전화: 911
- 상근: 97 625 999
- 선영: 91 12 54 26
이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.
입력
첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.
출력
각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.
예제 입력 1
2 3 911 97625999 91125426 5 113 12340 123440 12345 98346
예제 출력 1
NO YES