[python]백준 5052번 - 전화번호 목록

5052번: 전화번호 목록 (acmicpc.net)

5052번: 전화번호 목록

import sys

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

def insert_word(root, word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
        if node.is_end_of_word:
            return True  # 접두사인 단어가 이미 존재
    node.is_end_of_word = True
    return False

def main():
    input = sys.stdin.readline
    n = int(input())

    for _ in range(n):
        m = int(input())
        trie_root = TrieNode()
        check = False

        words = [input().rstrip() for _ in range(m)]
        words.sort()  # 길이 오름차순으로 정렬하여 검사

        for word in words:
            if insert_word(trie_root, word):
                check = True

        if check:
            print("NO")
        else:
            print("YES")

if __name__ == "__main__":
    main()

---

import sys
from collections import deque
input = sys.stdin.readline

n = int(input())

while n != 0:
    n-=1
    check = False
    m = int(input())

    arr = deque()
    for i in range(m):
        arr.append(input().rstrip())
    arr = deque(sorted(arr, key=len))

    for idx, i in enumerate(arr):
        if idx == m-1:
            break
        for j in range(idx+1,m):
            if arr[j].startswith(i):
                check = True
                break
        if check:
            break

    if check:
        print("NO")
    else:
        print("YES")

처음 시도인데요 이렇게 하면 시간초과 나와요

챗씨한테 어떻게 시간 줄일 수 있을까 해서 얻어낸 코드가 아래 코드입니다

import sys

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

def insert_word(root, word):
    node = root
    for char in word:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
        if node.is_end_of_word:
            return True  # 접두사인 단어가 이미 존재
    node.is_end_of_word = True
    return False

def main():
    input = sys.stdin.readline
    n = int(input())

    for _ in range(n):
        m = int(input())
        trie_root = TrieNode()
        check = False

        words = [input().rstrip() for _ in range(m)]
        words.sort()  # 길이 오름차순으로 정렬하여 검사

        for word in words:
            if insert_word(trie_root, word):
                check = True

        if check:
            print("NO")
        else:
            print("YES")

if __name__ == "__main__":
    main()

이게 Trie알고리즘을 이용한건데 아마도?? 처음 봐서 신기했습니당

[Python / 파이썬] Trie 알고리즘 : 네이버 블로그 (naver.com)

210126 개발일지(50일차) - 트라이(Trie) 알고리즘 개념 및 파이썬에서 구현하기(feat. Class) (velog.io)

여기 완전 설명 자세히 돼있으니 참고하면 좋을 거 같아요

 

위에 저처럼 하면 시간복잡도가 O(n)인데 Trie 알고리즘 이용하면 O(m)(m은 문자열 길이)만큼 걸린대요

김유진 방학 요약 ㅠ