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

0.  문제 링크

 

 

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

5052번: 전화번호 목록

---

1.  풀이 방법

 

 

굉장히 찝찝하게 풀었다.

정렬을 이용해서 풀었는데, 파이썬은 문자열을 길이가 아닌 사전 순대로 나열해서 정렬을 해준다.

그래서 정렬을 해서 직전 문자열이 다음 문자열의 부분이 되는가만 파악하면 된다.

 

나는 좀 거창한 풀이를 생각했는데, 생각보다 간단해서 허무했다.

사실 숫자의 트리를 만들어서 풀려고 했다.

예를 들어 911 다음에 91112가 들어온다면 기존에 생성된 9 - 1 - 1의 트리에서 뒤에 2만 붙이면 되는 방식이다.

결론적으로 리프노드가 전화번호의 개수보다 적다면 부분 문자열이 존재한다는 뜻이므로 NO를 출력하려고 했는데........

 

이 방식을 머릿속으로 골똘히 생각했다.

근데 문제는 전화번호 수가 최대 10,000개, 길이는 최대 10개이므로, 헤드 바로 아래는 최대 10개의 노드, 또 각각의 노드 아래에는 최대 10개의 노드....

이런 식으로 가다 보면 최대 10^10개의 리프 노드가 생성되는데, 이 상황에서 다시 탐색하면서 리프 노드의 개수를 센다? 이거는 아무리 생각해도 시간 초과가 난다고 생각했다.

 

아니면 중간에 하나씩 넣다가 기존에 존재하던 가지가 내 부분 문자열이거나, 내가 기존에 존재하던 가지의 부분 문자열일 때 NO를 출력하는 방식도 생각했었다.

근데 일단 10,000개를 또 숫자 하나씩 분리해서 트리에 넣는 것 또한 시간 복잡도가 상당히 클 것으로 생각해서 이 방법은 폐기하였다.

 

만약 트리로 푸신 분이 계시다면 어떻게 풀었는지 알려주십시오...

---

2.  코드

 

 

import sys
import heapq
input = sys.stdin.readline


if __name__ == "__main__":
    t = int(input())
    maps = list()
    for _ in range(t):
        n = int(input())
        maps.clear()
        for _ in range(n):
            maps.append((input().strip()))

        maps.sort()     # 사전 순서대로 정렬해줌

        for i in range(n - 1):
            cur = maps[i]
            nxt = maps[i + 1]
            if len(cur) < len(nxt):     # 뒤에 애가 더 길이가 길 때만 체크하면 됨
                if cur == nxt[:len(cur)]:
                    print("NO")
                    break
        else:
            print("YES")

---

3.  마무리