[백준 5052] 전화번호 목록 with Python

문제 링크

https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

풀이

import sys

t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	number = [sys.stdin.readline().strip() for _ in range(n)]
	number.sort()
	is_yes = True
	for i in range(1, n):
		if number[i].startswith(number[i-1]):
			is_yes = False
			break
	if is_yes: print("YES")
	else: print("NO")

전화번호를 문자열로 받아 정렬하면 911, 91125246 같은 전화번호는 서로 인접하게 된다.

만약 911, 9111, 91125246처럼 여러 개가 있어서 911과 91125246이 인접하지 않아도, 이미 911, 9111을 확인한 것 만으로도 이 전화번호 목록이 "일관성이 없음"을 알아낼 수 있다.

 

정렬된 전화번호를 순회하면서 현재 전화번호가 이전 전화번호로 시작하는지 여부를 확인하여 YES/NO 출력을 결정한다.