[3차] 자동완성

• 친절하게도 문제에 해설링크가 걸려있다. 해설은 좀 짧막하게 써있지만, 트라이 (Trie)를 쓰는 방법과 소팅을 쓰는 방법이 있다는 힌트만 있으면 사실 해법은 쉽게 나온다.
• 문제에서 요구하는 것은, 각각의 단어에 대해서, 다른 단어와 공유되지 않는 가장 짧은 접두사의 길이를 구하는 것.
• 공식 해설의 두 방법중 정해는 트라이이다. 트라이를 구성할때에 각 노드에, 차일드의 갯수를 저장하도록 구현하면, O(L)시간에 트라이를 생성하면서 각 노드마다 차일드의 갯수도 같이 구할 수 있다, 이제 각 단어의 모든 접두사를 순회하며 차일드가 한개밖에 없는 접두사중 가장 짧은 것의 길이를 구하는 것 역시 O(L)에 해결 가능.
  • Trie v2.0으로 업데이트하면서, 트라이를 생성할때에 차일드의 갯수를 저장하지는 않게 되었다. 하지만 트라이 생성 후에 다시 차일드의 갯수들을 구하는 것도 O(L)이라 복잡도에 차이는 없다
• 소팅을 하는 방법은, 소팅을 하고 나서는 인접한 단어들과만 비교하기 때문에, O(mn) ≈ O(L)시간에 비교가 가능하지만, 소팅에 O(mnlogn) ≈ O(Llogn)이 걸리므로 트라이보다는 시간 복잡도에서는 불리하다. (m은 각 단어의 평균 길이).
  • 하지만 트라이 (Trie)에서 언급했듯, 파이썬에서는 이 방법이 더 빠르게 동작할 것이다. (해보지는 않음)

"""Solution code for "Programmers 17685. [3차] 자동완성".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/17685
- Solution link: http://www.teferi.net/ps/problems/programmers/17685
"""

from teflib import string


def solution(words):
    trie = string.Trie(words)
    answer = 0
    for word in words:
        for i, node in enumerate(trie.prefixes(word)):
            if trie.word_count(node) == 0 and trie.get_child_count(node) == 1:
                answer += (i + 1)
                break
        else:
            answer += len(word)
    return answer

• Dependency: teflib.string.Trie