Skip to main content

5052 - 전화번호 목록

info

풀이 키워드​

스포주의

그래프 정렬 트라이


풀이 코드​

info
  • 메모리: 33432 KB
  • 시간: 128 ms
import sys
input = sys.stdin.readline

def solution():
    n = int(input())
    phone_book = []
    for _ in range(n):
        phone_book.append(input().rstrip())
    
    phone_book.sort()
    
    for i in range(n-1):
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            print('NO')
            return
        
    print('YES')
        

if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        solution()

풀이 해설​

트라이로 풀이할 수 있는 문제지만 구현이 빠른 단순 정렬로 풀이했다.

문자열 a가 b의 접두어라고 가정할 때, len(a) <= len(b) 임이 보장되므로

전화번호 목록을 오름차순 정렬하면 인접한 문자열끼리만 비교하여 접두어 존재 여부를 판단할 수 있다.


정렬을 이용한 풀이의 경우, sort()의 시간복잡도 + 탐색 시간복잡도를 생각하면

O(nlogn)O(nlogn) + O(n)O(n) = O(nlogn)O(nlogn)이 된다.