백준 - [Gold 4] 전화번호 목록

문제링크: www.acmicpc.net/problem/5052

5052번: 전화번호 목록

---

문제 설명

- T: 테스트 케이스 갯수

- N: 전화번호 개수

- N개의 전화번호가 주어짐

 

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

일관성이 있는것은 각 번호가 어떤 번호에도 접두어로 속하지 않는 경우를 뜻합니다.

 

ex)

911, 911234, 1023 => NO - 911이 겹치기 때문입니다.

12340, 123440, 123450 => YES  - 접두어가 되는 경우가 없습니다.

---

풀이

Trie로 풀려다가 더 간단한 방법으로 해결할 수 있는 문제였습니다. (Trie 자료구조 문제는 곧 풀 예정.... ㅎ)

해당 문제는 접두어인지만 확인하면 되는 문제로, 정렬 후 다음 문자에만 접두어인지 확인해주면 되는 문제입니다.

참고로, 정렬하지 않고 2차원 루프로 전체 검사하면 시간초과가 뜹니다.

 

코드

from sys import stdin
stdin = open("input.txt", "r")
# T: 테스트 케이스 개수
T = int(stdin.readline())
for t in range(T):
    # N: 전화번호 갯수
    N = int(stdin.readline())

    # 입력 받고 정렬
    phone_numbers = [stdin.readline().strip() for _ in range(N)]
    phone_numbers.sort()

    flag = 0
    for i in range(len(phone_numbers) - 1):
        # 접두어인지 확인
        if phone_numbers[i+1].startswith(phone_numbers[i]):
            print("NO")
            flag = 1
            break
    if flag == 0: print("YES")