[Python] BOJ(백준) 5052번 - 전화번호 목록

1. 링크

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

2. 난이도(solved.ac 참고)

골드4

3. 풀이(오답)

	import sys
	f = sys.stdin.readline
	T = int(f())
	for _ in range(T):
	answer = True
	n = int(f())
	candidate = [f().rstrip() for _ in range(n)]
	candidate.sort()
	min_num = candidate[0]
	for i in range(1, len(candidate)):
	if candidate[i][:len(min_num)] == min_num:
	answer = False
	if answer:
	print("YES")
	else:
	print("NO")

view raw 전화번호목록(fail).py hosted with ❤ by GitHub

처음에 접근을 잘못해서 여러번 틀렸다. sort를 한 뒤 처음 값을 기준으로 그 다음 값들부터 접두사에 처음 값이 들어가는지 여부로 판단을 했는데, 그렇게 하면 두번째 접두어가 세번째 입력의 접두어로 들어가있을 수 있기 때문에 접근이 잘못되었다.

1010
1234
12345

이런 경우가 있다고 해보면, 1010을 기준 값으로 잡고 1234부터 반복문을 진행하게 되는데, 이 경우 전부 1010이 들어가지는 않지만 1234는 12345에 들어가기때문에 NO가 나오는 게 정답이다. 근데 이전 코드대로 따르면 YES가 나왔다.

4. 풀이(정답)

	# https://www.acmicpc.net/problem/5052
	import sys
	f = sys.stdin.readline
	T = int(f())
	for _ in range(T):
	answer = True
	n = int(f())
	candidate = [f().rstrip() for _ in range(n)]
	candidate.sort()
	min_num = candidate[0]
	for i in range(len(candidate)-1):
	leng = len(candidate[i])
	if candidate[i+1][:leng] == candidate[i]:
	answer = False
	if answer:
	print("YES")
	else:
	print("NO")

view raw 전화번호목록.py hosted with ❤ by GitHub

위와 같은 반례가 있을 수 있기 때문에, 저 예시의 경우 1010과 1234를 비교, 그 다음 1234와 12345를 비교, 이런 식으로 진행이 되도록 바꾸었다. 이렇게 되면 sort를 했으므로 인접한 두 값은 만약 더 긴 값이 더 짧은 값을 포함하고 있다면 무조건 NO가 나올수밖에 없다.