[Problem Solving] BOJ 5052 : 전화번호 목록

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

 

입력받은 문자열에서 한 문자열이 다른 문자열의 접두어라면 NO를 출력, 그런 경우가 없다면 YES를 출력하는 문제이다.

위와 같은 자료구조를 Trie라고 한다.

우선 입력받은 문자열을 모두 Trie 구조에 삽입한다.

각각의 노드는 값과 자식 노드를 담는 리스트를 가지고 있다.

 

Trie 구조에 문자열 number를 삽입하는 과정은 다음과 같다.

1) 현재 노드의 자식 노드 중에서 number[0]와 같은 값을 가진 노드가 있다면, 그 노드에 number[1:]을 삽입한다.

2) 현재 노드의 자식 노드 중에서 number[0]와 같은 값을 가진 노드가 없다면 값이 number[0]인 새로운 노드를 만들어서 현재 노드의 자식 노드 리스트에 추가한다. 그리고 새로 만든 노드에 number[1:]을 삽입한다.

이 과정을 number[1:]가 빈 문자열이 될 때 까지 재귀호출 하는 것이다.

 

입력 받은 문자열을 모두 Trie구조에 넣고

입력받은 문자열 각각의 마지막 알파벳이 위치한 노드의 자식 노드 리스트를 반환하는 함수(아래 코드에서의 func)를 호출한다.

그 리스트에 담긴 노드가 하나라도 존재한다면 그 문자열은 어떤 문자열의 접두어인 것이다. 그러므로 NO를 출력하고,

그런 경우가 하나도 없다면 YES를 출력한다.

 

import sys

read = sys.stdin.readline

class Node:
    def __init__(self):
        self.value = None
        self.nextNodeList = []

    def insertNumber(self, number):
        if number == "":
            return
        
        nextNode = None
        for next in self.nextNodeList:
            if next.value == number[0]:
                nextNode = next
                break

        if nextNode is None:
            nextNode = Node()
            nextNode.value = number[0]
            self.nextNodeList.append(nextNode)

        nextNode.insertNumber(number[1:])

    def func(self, number):
        if number == "":
            return self.nextNodeList

        for next in self.nextNodeList:
            if next.value == number[0]:
                return next.func(number[1:])


def solution():
    n = int(read())
    numberList = []
    for i in range(n):
        inputNumber = read().rstrip()
        numberList.append(inputNumber)

    trie = Node()
    for number in numberList:
        trie.insertNumber(number)

    for number in numberList:
        if trie.func(number):
            print("NO")
            return
    
    print("YES")

t = int(read())
for _ in range(t):
    solution()