[BOJ 5052] 전화번호 목록 (Python)

풀이

처음에는 시간 초과가 발생하지 않을 것으로 예상하여 포인터 2개를 활용하여 비교 기준이 되는 번호가 비교대상 번호의 접두어가 되는지 판단하는 방식으로 접근하였다. 하지만, 시간 초과가 발생하였다...

문제의 포인트는 오름차순 정렬이다. 전화번호 목록에서 비교 번호가 바로 뒤에 있는 번호의 접두어인지만 확인하면 된다. 이는 정렬이 되었기에 해당 로직으로 전화번호 목록의 일관성을 파악할 수 있다.

트라이와 해시 자료구조를 이용한 풀이도 있다고 한다.

코드

import sys

input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N = int(input())
    phone_num = [input().rstrip() for _ in range(N)]

    # 전화번호 목록 오름차순 정렬
    phone_num.sort()

    flag = False
    for i in range(N - 1):
        # 비교 번호가 바로 뒤에 있는 번호의 접두어인 경우인지 확인
        # --> 정렬되었기에 이 조건만으로도 일관성을 판단할 수 있다.
        if phone_num[i] == phone_num[i + 1][0:len(phone_num[i])]:
            flag = True
            break

    if flag:
        print('NO')
    else:
        print('YES')