[Baekjoon] 5052번 : 전화번호 목록 (Python, 문자열, 정렬)

[Baekjoon] 5052번 : 전화번호 목록 (Python, 문자열, 정렬)

 

목차

 

 

 

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

5052번: 전화번호 목록

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

방법 1 - 메모리 30840KB / 시간 212ms / 코드 길이 335B

 

단순히 앞에 있는 것과 나머지 모든 것들을 다 비교하는 방식으로 코드를 풀었다면 $O(N^3)$가 되었을 것이고 시간초과를 보게 될 것이다.

그러나 본 문제는 접두어에 해당하는 부분에 대해서만 비교를 진행하고 이때 이를 용이하게 할 수 있는 것은 사전순으로 정렬하는 것에 있다.

 

즉, 두번째 예제는 ['113', '12340', '123440', '12345', '98346']와 같이 정렬된 상태에서 앞의 것과 바로 다음 것(i번째와 i+1번째)의 비교만으로 문제를 풀 수 있다. $O(N^2)$

 

다만 이렇게 정렬할 경우 문자 길이가 긴 것도 앞에 올수 있어 조건문에 위배될 수도 있다는 생각을 했지만 문제없이 돌아간 것을 보면 조건문에서는 상관 없다고 보인다.

if l[i] == l[i+1][:len(l[i])]:

 

i 번째 : '123440' (길이 6)

i+1 번째 : '12345' (길이 5)

 

 

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    l = [input().rstrip() for _ in range(n)]
    l.sort()
    flag = False
    for i in range(n-1):
        if l[i] == l[i+1][:len(l[i])]:
            flag = True
            break

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