[백준] 5052 전화번호 목록

문제

전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오.

전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.

예를 들어, 전화번호 목록이 아래와 같은 경우를 생각해보자

• 긴급전화: 911
• 상근: 97 625 999
• 선영: 91 12 54 26

이 경우에 선영이에게 전화를 걸 수 있는 방법이 없다. 전화기를 들고 선영이 번호의 처음 세 자리를 누르는 순간 바로 긴급전화가 걸리기 때문이다. 따라서, 이 목록은 일관성이 없는 목록이다.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 하나씩 주어진다. 전화번호의 길이는 길어야 10자리이며, 목록에 있는 두 전화번호가 같은 경우는 없다.

출력

각 테스트 케이스에 대해서, 일관성 있는 목록인 경우에는 YES, 아닌 경우에는 NO를 출력한다.

==

솔루션

• 어떤 전화번호가 다른 전화번호에 포함되어 있는지 체크
• 이 때 한 케이스당 최대 10,000개가 입력 될 수 있어서 한 요소에 대해 전체 요소를 체크하면 시간 초과가 발생

a = ["123","1223123"]
a.sort() // [ "1223123","123] 이 나옴 

b = ["91123231","911"] 
b.sort() // ["911","91123231"] 이 나옴

• 위와 같은 내장 정렬 함수의 특징을 이용해서 해당 배열을 정렬한 후 앞 뒤 요소만 비교해보면 앞의 전화번호가 이 다음 번호의 접두어가 되는지 체크 할 수 있음 ( 어떤 번호가 다른 번호의 접두어인지 전체 요소를 돌아보며 체크 할 필요가 X)

• 처음에 앞뒤 비교 할 때 in으로 판별했다가 시간 초과 뜸. in으로 따져보면 접두어가 아니라 전체 문자열을 탐색하니까 시간 초과

def solution(n, arr):
    arr.sort()
    for i in range(1, n):
        if arr[i-1] == arr[i][:len(arr[i-1])]: 
            return "NO"
    return "YES"


T = int(input().rstrip())

for _ in range(T):
    n = int(input().rstrip())
    arr = []
    for _ in range(n):
        a = input().rstrip()
        arr.append(a)

    print(solution(n, arr))