[Python] Trie - JuyeolRyu/CodingTest GitHub Wiki
1. Trie
- 문자열을 트리형태로 저장하고 효율적으로 탐색하기 위한 자료구조입니다.
- DFS를 사용해서 트리를 탐색해서 원하는 문자열을 탐색합니다.
2. Trie 풀이 과정
👉이미지 출처
- root를 [하위노드 개수,{자식노드}]의 구조로 생성해준다.
👉모든 노드는 아래의 구조로 생성한다.
root=[0,dict()]
- 단어와 root를 파라미터로 받아서 trie를 생성해주는 make_trie 함수를 생성한다.
def make_trie(root,word):
cur_node=root
#단어를 순서대로 탐색
for c in word:
#만약 노드에 현재 알파벳이 존재하지 않으면 생성
if c not in cur_node[1]:
cur_node[1][c]=[0,dict()]
#하위 노드개수+1
cur_node[0]+=1
#다음노드를 탐색하기 위해 현재노드를 다음노드로 변경해준다.
cur_node=cur_node[1][c]
#노드개수+1
cur_node[0]+=1
- make_trie 함수를 사용해서 trie를 생성해준다.
for word in words:
make_trie(root,word)
- 생성된 trie를 탐색하는 search_target 함수를 생성해준다.
def search_target(root,word):
ret=0
cur_node=root
#단어를 순서대로 탐색
for c in word:
#하위 노드가 없는 경우 탐색 횟수 반환
if cur_node[0]==1:
return ret
#탐색횟수+1
ret+=1
#현재노드를 다음노드로 변경
cur_node=cur_node[1][c]
#단어 끝가지 탐색해야하는 경우
return ret
for word in words:
answer += search_target(root,word)
3. Trie 코드
import sys
from collections import defaultdict
sys.setrecursionlimit(10**6)
def make_trie(root,word):
cur_node=root
for c in word:
if c not in cur_node[1]:
cur_node[1][c]=[0,dict()]
cur_node[0]+=1
cur_node=cur_node[1][c]
cur_node[0]+=1
def search_target(root,word):
ret=0
cur_node=root
for c in word:
if cur_node[0]==1:
return ret
ret+=1
cur_node=cur_node[1][c]
return ret
def solution(words):
answer = 0
root=[0,dict()]
for word in words:
make_trie(root,word)
for word in words:
answer += search_target(root,word)
return answer
4. 관련 문제