백준 5052 전화번호 목록 문제 풀이
문제 파악하기
문제의 목표는 주어진 전화번호들 중 어느 전화번호가 다른 전화번호의 시작 부분(접두어)가 되는지 확인하는 것입니다.
예시로 주어졌듯, 911은 91125426의 시작 부분이므로 문제의 표현에 따르면 “일관성이 없는 번호 목록“이라고 할 수 있습니다.
문제 풀어보기
조건에 따르면 최대 10자리 전화번호가 1만개 있는 전화번호 목록이 5회 주어질 수 있습니다. 따라서 순차적으로 두 전화번호를 뽑아 서로가 서로의 접두어인지 확인하는 방법을 사용하면 처리에 오랜 시간이 걸릴 것이 분명합니다. 문제의 목표 상 모든 전화번호는 최소 1회는 확인해야 하니, 최소 1회의 확인 과정 중 다른 번호와 접두어 관계인지 확인해야 합니다.
값을 순차적으로 확인할 수 있는 트리
트리를 사용하는 많은 알고리즘들은 값을 일정 조건에 따라 정렬한 뒤 노드들을 순차적으로 접근하는 방식으로 시간을 줄입니다. 대표적으로 이분 탐색 트리는 어떤 값에 대해 트리의 각 노드들보다 크거나 작은지 여부를 비교하며 값을 찾아나갑니다.
이 문제에서도 비슷한 방법을 사용할 수 있을 것입니다. 아래는 트리를 조금 차용한 개념 코드입니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Node:
def __init__(self):
# ends[i] = True : i로 끝나는 번호가 존재함
self.ends: list[bool] = [False for _i in range(10)]
# next[i]: 다음 자리 번호에 대한 노드
# i.e. '911' 확인중일 때, '9' 확인이 마무리되었다면 self.next[9]로 다음 노드 확인
self.next: list[Node] = [None for _i in range(10)]
...
number = '911'
# 트리의 루트 노드 (이미 다른 번호들이 모두 기록되었다고 가정)
node = Node(...)
i = -1
for each in number:
i = int(each)
# 앞에서부터 번호의 각 자리를 가져다 확인
if node.ends[i]:
# 현재 확인 중인 번호의 접두어가 전화번호 목록에 있음
else:
# 없다면 다음 노드로 이동
node = node.next[i]
node.end[i] = True
이 코드의 주 목표는 한 번 번호를 확인할 때, 번호에 대한 정보를 제 3의 자료구조에 저장하는 것입니다. 현재 확인 중인 번호의 시작 부분이 다른 번호를 포함하는지 확인하기 위해서는 확인 중인 번호를 앞에서부터 훑을 수 밖에 없으므로 유효한 방식입니다.
맵과 해시
1
2
3
4
5
number = 911
ends[9][1][1] = True
number = 9112345
if ends[9][1][1]:
break
번호를 앞에서부터 훑는 방식에서 다음 부분 번호를 확인하는 것은 앞부분 번호까지는 문제 상황을 확인하지 못했기 때문에 다음 순서로 넘어간 것입니다. 개념 코드에서도 채택한 방식인데, 여기서 착안해서 현재 확인 중인 수가 어떤 번호의 끝 부분으로 표시되어있다면 현재 번호와 어떤 번호는 “일관성이 없다”고 확인할 수 있습니다.
사실 이 아이디어는 클래스같은 것을 구현할 필요 없이 해시맵이나 그와 유사한 것으로 구현해낼 수 있습니다. 이러한 자료형은 어떠한 키 값에 대해 데이터를 바로 가져올 수 있으므로, 사실 앞에서 생각한 많은 과정을 생략하고 ends[전체 번호] = True 와 같이 구현하고 사용할 수 있습니다.
1
2
3
4
5
6
7
8
ends['911'] = True
number = '911234'
for i in range(1, len(number) + 1):
key = number[:i]
if ends[key]:
# 일관성 없음
break
ends[number] = True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
numbers.sort()
ends = {}
def query(number: str) -> bool:
ln = len(number)
for i in range(1, ln + 1):
key = number[:i]
if key in ends and ends[key]:
return False
ends[number] = True
return True
for number in numbers:
if not query(number):
return False
return True