반응형
programmers.co.kr/learn/courses/30/lessons/17685
코딩테스트 연습 - [3차] 자동완성
자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g
programmers.co.kr
해결 방법 : 트라이 자료구조
- 단어들을 각 문자를 기준으로 트라이에 저장
- 트라이 구성 단계에서 각 노드마다 접근 횟수 count
- 트라이를 완전탐색하며 입력 횟수 합산
- 특정 노드의 count가 1이면 더 이상 탐색할 필요 X
from collections import deque
class node:
def __init__(self, word=None):
self.w = word # 문자
self.c = 0 # 해당 노드까지 중첩 입력 횟수
self.children = dict()
class trie:
def __init__(self):
self.head = node(None) # 첫 노드 생성
def add(self, words):
cur = self.head
for w in words: # 각 문자
if cur.children.get(w) is None: # 문자 없으면 노드 생성
cur.children[w] = node(w)
cur = cur.children[w] # 다음 노드로 이동
cur.c += 1 # 입력 횟수 ++
def solution(words):
answer = 0
word_trie = trie() # 트라이 선언
for word in words: # 모든 단어 트라이에 추가
word_trie.add(word)
Q = deque([word_trie.head])
while Q: # bfs 완전 탐색
cur = Q.popleft() # 현재 노드
for w, n in cur.children.items():
answer += n.c # 다음 노드 n까지 문자까지의 입력 횟수 합산
if n.c > 1: # 다음 노드 n 이후에도 중복 문자가 있으면, 더 탐색
Q.append(n)
return answer
이전 풀이와 비교
: 트라이를 사용한 것은 똑같다. 완전 탐색방식은 이전에는 dfs, 이번에는 bfs로.
또한 최종 입력 횟수 산정 방법에 있어서,
이전 방식은 각 노드에 담고 있는 count를 사용하지 않고 dfs 호출 횟수를 추가적으로 이용했고,
따라서 단어의 마지막 문자가 저장된 노드를 표시하는 isword변수를 사용해야 했다.(비효율)
반응형