[Python] BOJ 5052 - 전화번호 목록(Phone List)

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

5052번: 전화번호 목록

# Trie(트라이) 자료구조를 사용해서 푸는 문제이다. (물론 그냥 내장함수 startswith을 사용해도 풀리긴 한다)

 

  * insert함수: string 문자열의 한 글자씩 트리의 children에 저장해주고 마지막 노드에는

                   전체 문자열인 string을 저장해준다.

 

  * search함수: string 문자열을 하나씩 돌며 트리의 children을 계속 방문한다.

                    문자열을 다 돈 뒤 current_node의 children이 존재한다면, string이 현재 트리에

                    있는 것이므로 False 리턴해준다.

 

  * 전화번호 목록을 phone 배열에 넣어주고 trie에도 넣어준다.

     phone안에 있는 전화번호들을 각각 search함수로 실행시키고 trie.search(p)가 False이면

     현재 전화번호가 다른 번호의 접두어인 경우므로 res = False로 바꿔주고 break해준다.

 

import sys
input = sys.stdin.readline
class Node:
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}

class Trie:
    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        current_node = self.head
        for char in string:
            if char not in current_node.children:
                current_node.children[char] = Node(char)
            current_node = current_node.children[char]

        current_node.data = string

    def search(self, string):
        current_node = self.head
        for char in string:
            current_node = current_node.children[char]
 
        if current_node.children:
            return False
        else:
            return True    

for _ in range(int(input())):
    n = int(input())
    trie = Trie()
    phone = []
    for _ in range(n):
        w = input().rstrip()
        phone.append(w)
        trie.insert(w)
    
    res = True
    phone.sort()
    for p in phone:
        if not trie.search(p):
            res = False
            break
    if res:
        print("YES")
    else:
        print("NO")

(solved.ac 티어: 골드 4)