문제 링크

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

문제 설명

• 주어진 전화번호 목록이 일관성이 있으면 YES
• 없으면 NO 출력

풀이

• 문자열 길이로 정렬 후 트라이 구현

파이썬 코드

import sys


class Node:
    def __init__(self, value=0, end=False):
        self.value = value
        self.end = end
        self.children = []

    def __str__(self):
        return f'{self.value} {self.end}'


def insert(root, num):
    curr = root
    i = 0
    while i < len(num):
        exist = False
        for j in range(len(curr.children)):
            child = curr.children[j]
            if num[i] == child.value:
                exist = True
                break
        if exist:
            if curr.children[j].end:
                return True
            curr = curr.children[j]
        else:
            curr.children.append(Node(num[i], i==len(num)-1))
            curr = curr.children[-1]
        i += 1
    return False



def solution():
    read = sys.stdin.readline
    t = int(read())
    for _ in range(t):
        n = int(read())
        numbers = [list(read().rstrip()) for _ in range(n)]
        numbers.sort(key=lambda x:len(x))

        root = Node()
        for num in numbers:
            exist = insert(root, num)
            if exist:
                break

        if exist:
            print('NO')
        else:
            print('YES')


solution()