[백준] 전화번호 목록 [코드 + 생각도 못했던 부분은?]

구현 & 문자열

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

5052번: 전화번호 목록

 

코드

import sys
input = sys.stdin.readline

t = int(input())

for i in range(t):
	n = int(input())

	number = [input().strip() for i in range(n)]

	number.sort()
	ori = True
	for j in range(len(number)-1):
		stand = number[j]
		if len(stand) > len(number[j+1]):
			continue
		if stand == number[j+1][:len(stand)]:
			ori = False
			break

	if not ori:
		print("NO")
	else:
		print("YES")

 

설명

 해당 문제는 문자열 관련 문제다. 우선 문제 내용상 크게 특별한 내용은 없다 '접두어'라는 뜻을 알아야 하고 '접두어'라는 뜻을 알게 된다면 풀이 자체는 금방 떠올릴 수 있는 문제다. 단 역시나 골드 문제 정도 되면 무언가 최적화가 필요하다거나 불필요한 코드는 없애게끔 해서 난이도를 올리는 것 같다... 다시 돌아와 해당 문제 핵심은 아래와 같다.

 

 

sort()를 얼마나 알고 있는가?

접두어를 알고 있는가?

 

 

 딱 두 문장으로 해당 문제를 풀 수 있는것 같다. 우선 두 번째부터 설명하려고 한다. 접두어는 단어나 문자 앞에 놓여 꾸며주게 되는 말인데 이를테면 풋사과에서 풋- 은 접두사라고 표현하게 되는데 이 문제랑 무슨 관련이 있는가 하면 해당 문제가 접두사까지만 검색을 요하기 때문이다. 즉 전화번호의 길이는 최대 10자리까지이고 그러면 접두어가 같으면 안 되기 때문에 접두어가 같다는 건 해당 길이만큼의 앞에 오는 말이 같아진다는 얘기가 된다. 그럼 최대 10자리를 비교했을 때 같은 단어라면 접두사가 같다고 표현할 수 있다. 하지만 해당 문제에서는 접두사가 같은 건 일관되지 않기 때문에 "NO"를 출력해야 한다. 따라서 접두사가 같지 않은 걸 찾는 게 핵심이다.

 

 첫번째 sort()를 얼마나 알고 있는가. 이전에 BFS문제를 풀 때 배웠던 거지만 람다에 정렬방식에 대해서 학습했었다 첫 번째 파라미터를 기준으로 우선정렬하고 이후 두 값이 같다면 두 번째 파라미터를 기준으로 정렬하는 방식을 작성했었다. 여기에서는 sort()를 얼마나 알고 있는지가 중요하다. 우선 알파벳 같은 경우 대문자-소문자 순서대로 정렬이 된다. 숫자 같은 경우에 크기 순서대로 정렬된다. 근데 왜 굵은색으로 칠했을까? 이 문제에서 받게 되는 자료형이 str일 경우 즉 Character 형태로 구성이 될 경우에 sort() 함수를 하게 되면 숫자의 크기 순서대로가 아니라 숫자의 우선순위대로 정렬이 되기 때문이다. 우선순위대로 정렬이 된다는건 2보단 1이 앞서고 3보단 2가 앞선다. 따라서 1, 2, 3으로 정렬이 될 수 있다는 걸 의미한다. 그게 이 문제와 무슨 관련이 있을까 필자도 해당 내용을 알지 못해 시간초과를 냈는데 단순하게 생각해 보면 숫자의 우선순위가 같다는 건 아래와 같은 경우를 생각해 보자.

 

 

9993

9923

9193

91934

 

 

 위 경우 Character 형태로 자료형을 입력을 받았다고 가정했을 때 sort() 함수를 사용하면 어떤 결과가 나올지 예상해 보면 우선 숫자의 우선순위대로 정렬이 된다라는 사실을 모른다고 가정하자. 그러면 숫자의 크기대로 보통 정렬된다고 생각한다. 그러면 당연히 아래와 같이 정렬이 될 것이다.

 

 

9193, 9923, 9993, 91934

 

 

 즉 숫자의 크기 순서대로 정렬이 된다. 오름차순으로 따로 reverse를 주지 않은 이상. 하지만 Character 형태로 숫자를 받았을 때 sort()로 정렬했을 경우에는 어떤 일이 일어나는가?

 

 

['9193', '91934', '99923', '9993']

 

 

 예상했던 기댓값이랑 너무 다르다. 두 번째 와있어야 할 9993이 맨 뒤에 있다. 그럼 무슨 차이가 있을까? 이제 숫자의 우선순위로 정렬된다라는 말을 이해할 수 있다. 91934, 9993 원래 9993이 91934위치에 있어야 하니까 그럼 둘 차이를 비교해보자. 둘의 차이는 두번째 숫자로 결정되게 된다. 앞자리는 9로 똑같고 그다음 자릿수는 1과 9다 즉 9보다 1이 우선순위가 높다. 따라서 91934가 두번째로 오게 되는 것이다. 그렇지만 아직까지 이게 왜 문제에 적용될 수 있는지에 대해서는 제대로 이해가 안된다면 첫번째 숫자와 두번째 숫자를 보자. 9193 과 91934의 공통점은 앞자리가 비슷한 값들이 정렬된다는 것이다. 이는 당연하다. 우선순위가 높은 순서대로 정렬되기 때문에 숫자를 비교해서 우선순위가 높은것들끼리 뭉쳐지게 될 것이고 그렇게 되면 9193까지는 동일하지만 동일한 숫자들 중에서는 가장 작은건 첫번째 숫자가 되게 된 것이고 두번째가 4가 된 것이다. 따라서 만약 9193이 앞 접두어로 같아지는 순간이 오게 된다면 그러면 숫자를 바꿔 9193, 9193이 연속으로 오게 될 것이다. 그렇다는 말은 접두어가 될 확률이 올라간다는 뜻이된다. 자릿수 하나하나가 접두어가 될 확률을 높이고 있기 때문이다. 4개의 숫자라면 첫번째 숫자가 맞게 될 경우 25% 두번째 숫자가 맞게 될경우 50% 세번째 숫자가 맞게 될경우 75%가 되는 것처럼 말이다. 결국 우선순위가 비슷한 숫자들끼리 모이게 되기 때문에 접두사를 비교적 빠르게 찾을 확률 또한 높아지게 된다.

 

 그리고 두 가지 정도 더 생각해 볼 수 있는데 사실 이 두 가지는 위에 사실을 알고 나서 생각해도 늦지 않기 때문에 위 과정이 더 중요하다. 일단 첫 번째는 "비교하려는 숫자가 비교하려고 하는 숫자보다" 길이가 크다면 이는 접두어가 있을 수 없다라는 사실이다. 비교하려는 숫자 같은 경우는 9193이라고 가정해보고 비교할려고 하는 숫자는 919라고 해본다면 비교하려는 숫자(9193)의 길이는 4, 비교할려고 하는 숫자의 길이는 (3) 그렇다면 이는 접두어가 같을 수 있는가? 접두어가 같을 수 없다. 길이가 다르기 때문에 따라서 길이가 작거나 같은 경우에만 가능하다는 것을 알 수 있고 접두어가 같다라는 건 비교하려는 숫자의 길이만큼을 다른 숫자에 대입해 봤을 때 그 길이 만큼이 같으냐 라는 의미다. 따라서 같게 된다면 일관성이 없는 것으로 판단이 된다는 것이다.