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

5052번: 전화번호 목록

import sys

input = sys.stdin.readline

t = int(input().rstrip())

for _ in range(t):
    n = int(input().rstrip())
    cases = []
    flag = True

    for _ in range(n):
        cases.append(input().rstrip())

    cases.sort()

    # for i in range(len(cases)):
    #     if flag:
    #         break
    #     for j in range(i+1,len(cases)):
    #         if cases[i] in cases[j]:
    #             flag = True
    #             break

    for i in range(len(cases)-1):
        if cases[i] == cases[i+1][:len(cases[i])]:
            flag = False
            break
    
    if flag:
        print("YES")
    else:
        print("NO")

 

이번 문제는 Testcase마다 전화번호 목록이 주어졌을 때, 다른 한 번호가 다른 번호의 접두어라면 "NO"를, 해당 하는 경우가 없다면 "YES"를 출력하는 문제이다.

 

처음에는 위에 주석으로 처리한 부분처럼 길이를 기준으로 정렬(sort)한 뒤에 2중 for문을 활용하여 풀이하려고 했었는데, 그렇게 되면 n + (n-1) + (n-2) .. 번의 연산으로 인해 결국 O(N^2)의 시간 복잡도를 가지게 되어 시간초과가 발생하게 된다.

 

다른 사람의 풀이를 참고해본 결과, 길이를 기준으로 정렬하는 것이 아니라 sort 함수에 인자 없이 문자열 배열을 정렬하면, 첫번째 문자를 기준으로 정렬하고 같으면 다음 문자를 기준으로, 또 같으면 다음 문자를 기준으로 정렬하는 방식이 된다.

 

결국, 한 번호가 다른 번호의 접두어라면, 배열을 정렬했을 때 그 두 번호는 인접해 있게 된다.

 

이를 이용해 배열을 정렬한 후 인접하고 있는 두 번호만 비교하면 1중 for문으로 일관성 없는 번호를 찾을 수 있다.

 

참고 : https://storing.tistory.com/49

[백준 5052번] 전화번호 목록 - 파이썬