[백준 14425번] 문자열 집합 (python/파이썬) - Trie 구현하기/defaultdict 쓰면 안되는 이유

Trie를 연습해볼 수 있는 대표적인 문제이다. 사실 python으로 푸는 경우 Trie를 이용하는 것보다 set을 이용하는게 더 빠르다 (이유는 set은 HashTable로 구현되어 있어, 원소 탐색에 선형시간이 걸리기 때문이라고 함). 심지어 python으로 하면 통과를 못하고, Pypy3으로 제출해야 한다. 나는 trie 연습을 위해 trie로 풀어 보았다.

 

Node의 children을 dictionary로 구현하는 것보다는 defaultdict로 구현하는 게 search에서 더 유리할 것 같다고 생각했는데,오히려 시간이 더 걸려서 그 이유를 알아보았다.

 

🌼 문제 링크

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

14425번: 문자열 집합

• 티어:  실버 III
• 분류: 자료구조, 문자열, 해시, 트리

 

 

❗ 코드 1. Defaultdict를 이용한 구현 (실패)

import sys
input = sys.stdin.readline

from collections import defaultdict

class Node:
    def __init__(self, data=False):
        self.data = data
        self.children = defaultdict(lambda: None)

def insert(head, string):
    ptr = head
    for s in string:
        if ptr.children[s] is not None:
            ptr.children[s] = Node()
        ptr = ptr.children[s]
    ptr.data = True
    
def search(head, string):
    ptr = head
    for s in string:
        if ptr.children[s] is not None:
            return False
        ptr = ptr.children[s]
    if ptr.data:
        return True
    else:
        return False

head = Node()

N, M = map(int, input().split())
for _ in range(N):
    insert(head, input().rstrip())
ctr = 0
for _ in range(M):
    if search(head, input().rstrip()):
        ctr += 1

print(ctr)

 

 

💡 코드 2. dictionary를 이용한 구현 (성공)

import sys
input = sys.stdin.readline

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

def insert(head, string):
    ptr = head
    for s in string:
        if s not in ptr.children:
            ptr.children[s] = Node()
        ptr = ptr.children[s]
    ptr.data = True
    
def search(head, string):
    ptr = head
    for s in string:
        if s not in ptr.children:
            return False
        ptr = ptr.children[s]
    if ptr.data:
        return True
    else:
        return False

head = Node()

N, M = map(int, input().split())
for _ in range(N):
    insert(head, input().rstrip())
ctr = 0
for _ in range(M):
    if search(head, input().rstrip()):
        ctr += 1

print(ctr)

 

코드 설명

• Trie를 이용한 구현이다. 
• 코드 1과 2의 차이점은 Node의 children을 저장하는 데에 defaultdict를 사용했냐, 일반 dictionary를 사용했냐의 차이밖에 없다.
• 때문에 search와 insert에서, children에 특정 문자가 있는지 검사하는 부분에서 차이가 발생한다.
  • 코드 1: if ptr.children[s] is not None
  • 코드 2: if s in ptr.children
• 결과: 코드 1 - 실패 (시간초과) / 코드 2 - 성공

 

 

 

코드 2의 경우는, 탐색에 ptr.children의 길이만큼의 시간이 소요될 것이라 생각했고,

코드 1의 경우는, 탐색에 O(1) 시간이 소요될 것이라 생각했다.

하지만 결과는 반대로, 코드 1은 시간초과가 발생했고 코드 2는 통과했다.

 

 

백준 질문게시판에 글을 올려서 다음과 같은 답을 얻을 수 있었다.

 

각 node의 key가 알파벳 26자로 제한되어 있기 때문에, children의 최대갯수 역시 26개로 제한된다.

따라서 코드 2에서 ptr.children의 탐색이 O(n)이라도 n이 최대 26으로 매우 작고,

코드 1의 경우 탐색에 O(1)이라도 그 상수가 커서 코드 2의 선형탐색보다 느려질 수도 있다는 것이다.

 

 

코드를 짤 때 시간복잡도 외에도 n의 크기도 함께 고려해야 한다는 것을 느낀 하루..