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

문제 링크 : https://www.acmicpc.net/problem/5052

5052번: 전화번호 목록

 

1. 접근 방법

가장 쉬운 방법은 각 전화번호를 길이별 오름차순 정렬하여 해결하는 방법이다. 각 테스트 케이스 별 입력도 10000개 이고, 정렬, 탐색을 고려한다고 해도 더 빠르게 작동할 것이다.

하지만 이번 문제는 트라이 알고리즘으로 해결하고 싶었다. 처음에는 무슨 알고리즘인가 하여 찾아보고 고민도 했는데, 오히려 구현은 이러한 과정보다 더 쉽게 해결됐다.

 

 

2. 해결 코드

• 파이썬 풀이 코드

import sys
input = sys.stdin.readline


for _ in range(int(input())):
    n = int(input())
    # 각 점에 대하여 점을 키, 자식을 값으로 저장하는 딕셔너리
    # 각 점이 번호의 끝일때 True로 저장
    num_tree = {'-1': [False, set()]}
    
    # 다른 번호의 접두어가 되는 번호가 있는지
    prefix_exist = False
    for __ in range(n):
        phone_number = tuple(input().strip())
        if prefix_exist:
            continue
        for i in range(len(phone_number)):
            prefix = ''.join(phone_number[:i])
            now = prefix + phone_number[i]
            # 접두어는 이미 등록되어 있으므로, 각 값의 첫 번째가 True인지 확인
            if i != 0 and num_tree[prefix][0]:
                prefix_exist = True
                break
            # 탐색
            if i == 0:
                if now in num_tree['-1'][1]:
                    continue
                else:
                    num_tree['-1'][1].add(now)
                    num_tree[now] = [False, set()]
            else:
                if now in num_tree[prefix][1]:
                    continue
                else:
                    num_tree[prefix][1].add(now)
                    num_tree[now] = [False, set()]
        # 마지막 전체 번호 확인
        else:
            # now는 이정에 저장한 것 그대로 사용 가능
            if num_tree[now][1]:
                prefix_exist = True
            else:
                num_tree[now][0] = True
    
    if prefix_exist:
        print('NO')
    else:
        print('YES')

• 풀이 과정

우선, 트라이 구조를 만들었다. 트라이는 주로 문자열에서 가장 앞부터, 순서대로 하나씩 추가하며, 하나의 문자열을 트리 형태로 늘어뜨리는 것이다.

밑의 위키피디아 링크의 예시에 따르면, 'ted'에 대하여 't', 'te', 'ted', 'tea'에 대하여 't', 'te', 'tea'로 이어지는 트리 형태를 가진다.

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85) 

트라이 (컴퓨팅) - 위키백과, 우리 모두의 백과사전

이번 문제에서 2번째 테스트 케이스의 113, 12340, 123440, 12345, 98346을 형상화하면 다음과 같이 된다.

 

 

루트 점에서부터 각 숫자를 앞에서부터 1자리, 2자리, ..., n자리 까지를 자식으로 갖게 하여 그래프를 구성한다. 세부적인 트리 생성에는 다양한 방법이 있겠지만, 나는 루트를 -1로 시작을 했고, 각각이 접두어인지 확인을 해야 하기 때문에, 각 숫자가 끝나는 지점에서 True를 표시해뒀다.

루트를 -1로 정한 것은 각 자리는 무조건 자연수이므로 나올 수 없는 숫자여서 그렇다. 빈 문자열이나 다른 방법도 가능할 것 같다.

각 수를 딕셔너리의 키로, 값으로는 어떤 숫자가 끝나는 지를 표시하는 True or False, 자식을 담는 set으로 했다.

모든 숫자를 순회하며 각 키를 탐색, 자식에 해당하는 숫자가 있는지 확인하고, 없으면 추가하는 방식으로 진행했다. 만약에 숫자가 끝난다면 True를 표시한다.

접두어가 되는지를 확인할 때 2가지로 나누어서 했다. 첫 번째로 각 숫자로 트리를 구성해가며 값으로 오는 첫 번째 값이 True인 것을 만나게 되면 접두어를 만나게 되므로 종료한다. 두 번째로 각 숫자를 끝까지 탐색했을 때, 해당 숫자가 다른 숫자의 접두어가 되는 경우도 있다. 이때는 해당 숫자를 키로 하는 딕셔너리의 값의 두 번째 값인 자식 set을 확인하여 set이 비어있지 않으면 해당 숫자가 다른 숫자의 접두어가 되어 종료한다.

• 주의 : 모든 번호를 입력을 받고 진행한다면 괜찮지만, 내가 한 것처럼 각 숫자를 하나씩 받으며 진행한다면, 접두어가 있음을 찾았을 때, 바로 종료하게 되면 다른 번호를 넘기지 않아 입력에 있어 오류가 발생한다

 

3. 생각 정리

새로운 알고리즘을 공부하는 것은 매우 기대되는 작업이면서 힘든 작업이 되기도 한다.

트라이 알고리즘은 구현하는 과정이 즐거웠다. 트라이 구조를 변경하면, 세그먼트 트리를 변경하여 최대, 최소, 합 등을 구하는 것처럼, 다양하게 응용할 수 있을 것 같다.