포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다. 효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.
예를 들어, 학습된 단어들이 아래와 같을 때
* go
* gone
* guild
go를 찾을 때 go를 모두 입력해야 한다.
gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.
이 경우 총 입력해야 할 문자의 수는 7이다.
라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.
학습과 검색에 사용될 중복 없는 단어 N개가 주어진다. 모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.
2 <= N <= 100,000
2 <= L <= 1,000,000
출력 형식
단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.
입출력 예
words
result
["go","gone","guild"]
7
["abc","def","ghi","jklm"]
4
["word","war","warrior","world"]
15
풀이
LV 4 문제 중 최약체 문제라고 개인적으로 생각한다. 사용해야 할 자료구조 개념만 확실히 잡고 있으면 그리 어려운 문제는 아니기 때문이다.
이러한 문자열 분류 등의 작업에는 트라이 자료구조가 제일 효율적이다. 또한 자동완성이 확정적으로 완료되는 조건은 더 이상의 입력이 필요 없을 때, 즉 계속 진행할 경우 나타나는 리프 노드가 단 하나일때 뿐이다. 따라서 트라이 자료구조를 통해 words의 문자열을 저장하고, 탐색을 통해 각 노드에 도달할 수 있는하위 리프 노드 개수를 저장한다. 그리고 자동완성이 완료되는 시점은 words를 탐색하며 리프 노드 개수가 1이 되는 순간의 depth가 된다. 트라이 자료구조는 파이썬의 경우 dictionary를 사용하면 편하다.
풀이 코드
import sys
sys.setrecursionlimit(1000000)
def leaf_search(_dict) :
if not _dict :
return 0
result = 0
for key, in _dict.keys() :
_dict[key][0] += leaf_search(_dict[key][1])
result += _dict[key][0]
return result
def solution(words):
word_dict = dict()
for word in words :
cur_dict = word_dict
for idx, w in enumerate(word) :
if w not in cur_dict :
cur_dict[w] = [0, dict()]
if idx == len(word)-1 :
cur_dict[w][0] += 1
cur_dict = cur_dict[w][1]
leaf_search(word_dict)
answer = 0
for word in words :
cur_dict = word_dict
for idx in range(len(word)) :
if cur_dict[word[idx]][0] == 1 :
break
cur_dict = cur_dict[word[idx]][1]
answer += idx+1
return answer
지금 프로그래머스에 답안 제출이 잘 되지 않아서, 풀이 완료 인증은 추후 업로드 예정이다...