[BOJ / Python] 5052- 전화번호 목록 / 문자열, 정렬

5052번: 전화번호 목록

전화번호 목록이 주어진다.

n = 전화번호의 수

목록들 중 한 번호가 다른 한 번호의 접두어인 경우 그 전화번호부는 일관성이 없는 목록이니 NO, 아니면 YES를 출력하는 문제다.

 

풀이

완전탐색은 시간초과가 뜬다. 전화번호의 수 n이 최대 10,000개이기 때문에 최악의 경우 50 * 10,000 * 10,000 * 10으로 어마어마한 숫자가 나와버린다.

 

힌트는 문자열 정렬이다.

숫자를 문자로 입력 받고 정렬하면 이렇게 된다.

숫자와 결과가 다르다!

124,225,227,22534를 정렬한 결과
124, 225, 22534, 227

그렇기 때문에 n-1번 반복하며 앞뒤만 비교해 주면 된다.

 

숫자를 문자형으로 받아 정렬하면 어떻게 되는지 안다면 쉽게 푸는 문제였다.

다른 문제에도 적용할 만 하니 기억해 두자.

코드

from sys import stdin
def check(numbers):
    for i in range(len(numbers)-1):
        if numbers[i+1].startswith(numbers[i]): # 방법 1
        # if numbers[i] == numbers[i+1][:len(numbers[i])]: # 방법 2
            print('NO')
            return
    print('YES')

t = int(input())
for _ in range(t):
    n = int(input())
    numbers = []
    for i in range(n):
        numbers.append(stdin.readline().strip())
    numbers.sort()
    check(numbers)

 

설명에 부족한 부분, 틀린 부분 지적 감사히 받습니다.