[BOJ] 14425. 문자열 집합(Python) / Trie 자료구조

14425번: 문자열 집합

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

매주 알고리즘 코딩 & 컴공 전공 스터디를 진행하는데, BFS, DFS, 백트래킹, Brute Force, Greedy 등은 자주 푸니까 매주 한 개씩 새로운 알고리즘을 공부해보자 하여 지난 주 이분탐색에 이어 이번 주는 트라이 자료구조에 대해 한번 공부해보기로 했다. 사실 난 처음 들어봤지만, 뭔지 궁금하여 해보자 했다!

• 사용 자료구조 : Trie 
• 트라이 자료구조 => 파이썬 딕셔너리를 활용해 클래스 객체(노드)를 생성한다. 
• 문자별로 key, data, children을 가진다.
• Trie 객체를 생성하는 클래스 내에 삽입(Insert), 탐색(Search) 함수를 만든다.
• 나보다 훨씬 정리를 잘해놓으신 분의 블로그를 참고해 클론 코딩해봤다.
• 링크는 아래 첨부한다. 아래 링크의 포스팅 내에 그림이 있는데, 이해를 도울 것이다.

youseop.github.io/2020-11-09-BAEKJOON-14425_%EB%AC%B8%EC%9E%90%EC%97%B4%EC%A7%91%ED%95%A9/

 

파이썬 코드는 다음과 같다. 1) Trie 자료구조 구현 + 2) Set으로 풀이 + 3) Dictionary로 풀이 총 3가지 방법으로 푼 코드다.

---

from sys import stdin
input = stdin.readline

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}

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

    # 문자열 삽입
    def insert(self, string):
        curNode = self.head
        # 삽입할 string 각각의 문자에 대해 자식 Node를 만들며 내려간다.
        for char in string:
            # 자식 Node들 중 같은 문자가 없으면 Node 새로 생성
            if char not in curNode.children:
                curNode.children[char] = Node(char)
            # 같은 문자가 있으면 해당 노드로 이동
            curNode = curNode.children[char]
        curNode.data = string

    # 문자열이 존재하는지 탐색
    def search(self, string):
        curNode = self.head

        for char in string:
            if char in curNode.children:
                curNode = curNode.children[char]
            else:
                return False
        
        if curNode.data != None:
            return True

# main
N, M = map(int, input().split())

# 방법 1 - Trie 자료구조 구현(5908ms)
wordTrie = Trie()           # 주어진 단어의 정보를 저장할 Trie 객체 생성
lenWord = [False] * 501     # 주어진 문자열과 길이가 같은 문자열에 대해서만 탐색 진행

for _ in range(N):
    word = input().strip()
    wordTrie.insert(word)   # 트라이에 단어 삽입
    lenWord[len(word)] = True

result = 0      # 단어 찾은 갯수
for _ in range(M):
    word = input().strip()
    if not lenWord[len(word)]:   # 문자열 길이 다르면 탐색 X
        continue
    if wordTrie.search(word):    # 문자열 길이 같으면 탐색 O
        result += 1
print(result)

------------------------------------------------------------------------------------------
# 방법 2 - 그냥 Set 사용(320ms)
# wordSet = {input().strip() for _ in range(N)}

# find = 0
# for _ in range(M):
#     word = input().strip()
#     if word in wordSet:
#         find += 1
# print(find)

# 방법 3 - 그냥 딕셔너리 사용(300ms)
# wordDict = {input().strip(): 1 for _ in range(N)}

# find = 0
# for _ in range(M):
#     word = input().strip()
#     if word in wordDict.keys():
#         find += 1
# print(find)

---

• 시간 : 5908ms / 메모리 : 2,096,768kb
• 고찰 : 트라이로 구현한 코드가 Set, Dictionary로 구현한 것보다 후어어어어어어러러럴씬 시간, 공간 복잡도가 많이 들더라,, 그래도 사용하는 이유가 있을 것이니.. 지금 나가봐야 해서 나중에 좀더 공부해보도록 하자.