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

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

5052번: 전화번호 목록

 

모든 문자열 비교를 해야 하나.. 그치만 시간초과가 날텐데...

 

하면서 고민했다.

 

그런데 정렬을 하게 되면 접두사가 같은 것끼리 뭉치게 된다.

이렇게 되면 n*n이 아니라 n번의 비교로 끝낼 수 있다.

 

"정렬"을 잘 활용하자

 

import sys


def solve(n, arr):
    for i in range(n - 1):
        l = min(len(arr[i - 1]), len(arr[i]))
        for j in range(l):
            if arr[i - 1][j] != arr[i][j]:
                break
        else:
            return "NO"
    return "YES"


t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    arr = [sys.stdin.readline().strip() for _ in range(n)]
    arr.sort()
    print(solve(n, arr))