글 읽기 - 파이썬 Trie 시간초과 관련 질문입니다.

jwjung0907 1년 전 1

Trie 자료구조를 구현해서 문제를 풀어보려고 했습니다...

처음에 구상할 때 아래 코드 처럼 insert에서 중복(leaf)을 확인하면 바로 return하여 그 케이스를 끝내는 형식을 하였는데, 시간초과를 받았고,

이후 insert와 비슷한 check 매서드를 만들어 모든 데이터의 insert를 마친 후에 check하는 식으로

바꿔보았더니 통과를 받았습니다. 이때 insert 메서드는 바꾸지 않고, leaf(문자열 끝)이면 return하는 식 그대로 했습니다.

단순히 봤을 때는 바꾼게 더 시간이 많이 걸릴 것 같은데...

어떤 차이점이 있어 시간초과가 나는지 잘 모르겠습니다..

import sys
read = sys.stdin.readline


class Node:
    def __init__(self):
        self.data = {}
        self.leaf = False


class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, _list):
        current = self.root
        for num in _list:
            if current.leaf:
                return False
            if num not in current.data:
                current.data[num] = Node()

            current = current.data[num]

        current.leaf = True
        return True


for _ in range(int(read())):
    N = int(read())
    trie = Trie()
    phone_list = [read().strip() for _ in range(N)]

    for p in phone_list:
        if not trie.insert(p):
            print("NO")
            break
    else:
        print("YES")

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

파이썬 Trie 시간초과 관련 질문입니다.

jwjung0907 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말