전화번호 목록 (5052번) - 백준 (BOJ)

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

5052번: 전화번호 목록

 

 

백준 - 전화번호 목록 (Phone List) (5052번)

 

난이도 : Gold 4

알고리즘&자료구조 : Trie (트라이) / Sorting(정렬)

시간복잡도 : O( N )

 

 

import sys
input = sys.stdin.readline


def is_consistent(n):
    memo = {}
    nums = [input().rstrip() for _ in range(n)]
    for num in nums:
        res = False
        cur = memo
        for d in num:
            if '-1' in cur:  # ②
                return 'NO'
            if d not in cur:  # ③
                res = True
                cur[d] = {}
            cur = cur[d]
        if not res:  # ④
            return 'NO'
        cur['-1'] = {}  # ①
    return 'YES'  # ⑤


if __name__ == '__main__':
    print('\n'.join(is_consistent(int(input())) for _ in range(int(input()))))

 

 

정렬 또는 트라이 (Trie) 를 활용해서 풀 수 있는 문제이다.

오랜만에 Trie로 풀어보았다.

 

트라이에 대한 설명

 

 

---

 

① 각 문자열이 끝나는 부분을 -1로 표시했다.

 

② 만약 어떤 문자열이 중간에 -1을 만난다면,

현재까지의 접두사가 다른 문자와 겹친다는 의미이므로

'NO' 를 반환한다.

 

③ 만약 어떤 문자열이 -1을 만나지 않고,

중간에 새로운 루트를 생성한다면,

그 문자는 다른 문자열과 겹치지 않는다.

 

④ 만약 어떤 문자열이 단 한 번도 새로운 루트를 생성하지 않았다면,

그 문자는 다른 문자열의 접미사가 되므로,

'NO' 를 반환한다.

 

⑤ 모든 문자열을 탐색하고, 'NO'를 반환한 적이 없다면

해당 테스트케이스는 일관성이 있으므로

"YES" 를 반환한다.