개요
문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조입니다.
일반적으로 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행합니다. 특징은 아래와 같습니다.
- N진 트리: 문자 종류의 개수에 따라 N이 결정됩니다. 예를 들어 알파벳은 26개의 문자로 이뤄져 있으므로 26진 트리로 구성됩니다.
- 루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지합니다.
구현 방법
- 루트 노드는 공백을 유지한 채 첫 단어에 해당하는 노드를 생성합니다.
- 아래 과정을 각 단어에 대해 반복하여 단어들을 모두 트리에 입력합니다.
- 현재 위치한 글자에 대해 루트 자식노드 중 해당 글자가 공백 상태가 아니면 해당 글자로 이동합니다. 공백 상태라면 글자를 추가하고 그곳으로 이동합니다.
백준 14425 파이썬
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
class Node(object):
def __init__(self, is_end):
self.is_end = is_end
self.child_node = {}
class Trie(object):
def __init__(self):
self.parent = Node(None)
# 문자 삽입
def insert(self, string):
now_node = self.parent
temp_length = 0
for char in string:
# 자식 노드들이 미생성된 문자열이면 새로 생성
if char not in now_node.child_node:
now_node.child_node[char] = Node(False)
now_node = now_node.child_node[char]
temp_length += 1
if temp_length == len(string):
now_node.is_end = True
# 문자열이 존재하는지 탐색
def search(self, string):
now_node = self.parent
temp_length = 0
for char in string:
if char not in now_node.child_node:
break
now_node = now_node.child_node[char]
temp_length += 1
if temp_length == len(string) and now_node.is_end:
return True
return False
my_trie = Trie()
for i in range(N):
word = input().strip()
my_trie.insert(word)
cnt = 0
for i in range(M):
word = input().strip()
if my_trie.search(word):
cnt += 1
print(cnt)
'컴퓨터 공학 분야 별 지식 > 개념(파이썬)' 카테고리의 다른 글
파이썬 코딩테스트 합격을 위한 팁 정리 (0) | 2024.03.22 |
---|---|
이진 탐색(binary search) 알고리즘 파이썬, 백준 2343 파이썬 (2) | 2024.03.22 |
최단거리 찾기 3 - 플로이드-워셜(floyd-warshall) 파이썬, 백준 11404 파이썬 (0) | 2024.03.22 |
최단거리 찾기 2 - 벨만-포드(bellman-ford-moore) 파이썬, 백준 11657 파이썬 (1) | 2024.03.18 |
K번째 최단 거리 찾기 파이썬, 백준 1854 파이썬 (1) | 2024.03.11 |