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

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

5052번: 전화번호 목록

---

 문제 풀이

문자열 문제이다.

 

문자열 정렬의 특징을 잘 활용하면 된다.

숫자는 정렬하면 크기대로 정렬이 되지만 문자열은 사전 순으로 정렬된다!!

예를 들어서 [123, 12, 1245]는 12, 123, 1245 순으로 정렬되지만,

['235', '12', '1245']는 '12', '1245', '235' 순으로 정렬된다!

따라서 앞뒤로 비교만하면 쉽게 확인할 수 있다.

 느낀 점

트라이로 풀 수 있다고 하는데.. 나중에 공부하는 걸로...

특징만 생각해내면 간단한 문제였는데 생각하지 못해서 한참을 헤맸다.

처음에는 같은 번호가 없기 때문에 자릿수만 생각해서 비교해주려고 했다.

하지만 2중 반복문이 나오기 때문에 절대적으로 시간 초과가 발생할 것을 예상하고 방향을 틀었다.

 코드

import sys
input = sys.stdin.readline

def check(nums):
    for i in range(len(nums)-1):
        if nums[i] == nums[i+1][:len(nums[i])]:
            print('NO')
            return
    print('YES')

t = int(input())
for _ in range(t):
    n = int(input())
    nums = [str(input().strip()) for _ in range(n)]
    nums.sort()
    
    check(nums)