🥈 14426번: 접두사 찾기

👉🏻 14426번: 접두사 찾기

import sys; input=sys.stdin.readline
from collections import defaultdict

class Node(object):
    def __init__(self):
        self.is_terminal = False
        self.children = defaultdict(Node)

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

    def insert(self, string):
        node = self.root
        for char in string:
            node = node.children[char]
        node.is_terminal = True

    def search(self, string):
        node = self.root
        for char in string:
            if char not in node.children:
                return False
            node = node.children[char]
        return True

n, m = map(int, input().split())
s = [input().strip() for _ in range(n)]
prefix = [input().strip() for _ in range(m)]

trie = Trie()

for word in s:
    trie.insert(word)

count = 0
for word in prefix:
    if trie.search(word):
        count += 1

print(count)

• startswith()로 풀어보려다가 시간 초과 때문에 Trie 자료구조를 이용하여 풀어낸 문제입니다.
• 우선 Trie는 트리 형태로, 부분 문자열들을 각각 노드로 저장하고 탐색할 때 효율적으로 사용되는 자료구조입니다.
• defaultdict를 사용하여 시간을 조금 더 단축시켰고, Trie class도 기존보다는 조금 단순화시켰습니다.
• Trie 자료구조에 대해서는 추후 글을 작성해서 올려보도록 하겠습니다!