[ 백준 ][ 골드3 ] 5052번 - 전화번호 목록 ( 파이썬 )

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

5052번: 전화번호 목록

1. 문제

---

2. 코드

---

      

      

      

    
    

      <python />
    
import sys
input = sys.stdin.readline
T = int(input())
for test_case in range(T):
    n = int(input())
    arr = sorted([input().rstrip() for _ in range(n)])
    for i in range(n-1):
        if arr[i] == arr[i+1][:len(arr[i])]:
            print("NO")
            break
    else:
        print("YES")

3. 풀이

---

원래는 트라이라는 자료구조로 분류되어 있지만 트라이를 사용하지 않고도 한 가지 간단한 아이디어로 해결이 가능하다.

• 어떤 문자열 A가 다른 문자열B의 접두어라는 것은 여러 조건을 포함한다.
  1. A 문자열은 길이가 B 문자열보다 짧다.
  2. B 문자열이 A문자열로부터 시작한다. 
• 이를 모두 통틀어 한 번에 적용시키는 방법은 사전순 정렬이다.
• 사전순으로 정렬된 배열에서 현재 문자열이 포함될 수 있는 가장 빠르고 필수적인 문자열은 다음 인덱스의 문자열이다.
• 예를 들어, 0번 문자열은 1번 문자열의 접두어가 아니라면 2번 문자열의 접두어가 될 수 없다.
• 왜냐하면 사전순 정렬에 의해 맨 앞부터 검사하여 정렬했기 때문이다.

이런 아이디어를 통해 쉽게 해결가능한 문제였다.