프로그래머스 자동 완성 (python, 파이썬)

• 문제 설명

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, 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

---

• 코드

def make_trie(words):
    dic = {}
    for word in words:
        current_dict = dic
        for letter in word:
            current_dict.setdefault(letter, [0, {}])
            current_dict[letter][0] +=1              
            current_dict = current_dict[letter][1]
            
    return dic

def solution(words):
    answer = 0
    trie = make_trie(words)
    for word in words:
        temp = trie
        for letter in word:
            answer += 1
            temp = temp[letter]
            if temp[0] == 1:
                break
            else:
                temp = temp[1]
    
    return answer

{'g': [3, {'o': [2, {'n': [1, {'e': [1, {}]}]}], 'u': [1, {'i': [1, {'l': [1, {'d': [1, {}]}]}]}]}]}

 

이런식으로 trie구조를 이용해서 탐색해야지 시간초과가 발생하지 않는다.

단어를 탐색하다가 값이 1인경우에는 뒤로 더이상 탐색할수 없기때문에 break로 탈출하고 아니면 계속해서 탐색해준다.

---

• 출처

https://programmers.co.kr/learn/courses/30/lessons/17685?language=python3