[정렬 문제] 백준 5052번: 전화번호 목록

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

5052번: 전화번호 목록

 

첫 시도)

test = int(input())

def check(lst):
    for i in range(len(lst)):
        length = len(lst[i])
        for j in range(i + 1, len(lst)):
            if lst[i] == lst[j][:length]:
                return 'NO'
    return 'YES'

for _ in range(test):
    n = int(input())
    numbers=[]
    for i in range(n):
        numbers.append(input())
    numbers = sorted(numbers, key=len)
    print(check(numbers))

접두사를 찾아야 하기 때문에 길이순 정렬을 하고 접두어를 판별했다.

완전탐색이라 시간 초과에 걸렸다.

 

test = int(input())

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

for _ in range(test):
    n = int(input())
    numbers=[]
    for i in range(n):
        numbers.append(input())
    numbers = sorted(numbers)
    print(check(numbers))

도저히 모르겠어서 구글링..

그런데 길이순이 아닌 문자열 정렬을 해주면 바로 옆만 확인해봐도 된다.