[programmers] Level4. 자동완성

https://programmers.co.kr/learn/courses/30/lessons/17685

코딩테스트 연습 - [3차] 자동완성

풀이

• Trie 자료구조를 활용
• 먼저 단어를 Trie에 넣음. 그리고 Trie에서 단어를 찾을 때 각 단어마다 입력해야 할 문자 수를 어떻게 찾을지 생각해야 함.
  • 기본이 되는 Node를 만들 때, data, children 외에 below_word_counts를 추가해 해당 단어 밑에 단어가 몇 개가 남았는지 개수를 저장.
  • 처음 insert할 때 below_word_counts 변수를 항상 1씩 증가시켜 Node 밑에 몇 개의 단어가 있는지 알 수 있게 함.
• 입력해야 할 문자 수를 찾을 때 두 가지 조건을 생각함.
  • 먼저 depth 변수를 추가해 children node로 나아갈 때마다 1씩 증가. 타이핑한 문자 개수로 볼 수 있음.
  • 첫 번째 조건으로 len(word) == depth일 경우 depth를 리턴. 입력된 문자를 다 타이핑한 경우로 볼 수 있고, 'go', 'gone'과 같이 짧은 단어가 긴 단어에 포함될 경우, 해당 조건식이 실행됨
  • 두 번째 조건으로 현재 Node 밑에 남아있는 단어가 1일 경우에 depth를 리턴. 현재 노드까지 타이핑한 경우, 유일한 단어가 1개 남아있기 때문에 자동완성이 적용될 수 있음. depth를 리턴.

class Node:
    def __init__(self, data=None):
        self.data = data
        self.children = {}
        self.below_word_counts = 0

class Trie(object):
    def __init__(self, words):
        self.header = Node()
        for w in words:
            self.insert(w)

    def insert(self, word):
        cur = self.header
        for w in word:
            if w not in cur.children:
                cur.children[w] = Node(w)
            cur.below_word_counts += 1
            cur = cur.children[w]
        cur.below_word_counts += 1

    def count_typing_words(self, word):
        cur = self.header
        depth = 0
        for w in word:
            cur = cur.children[w]
            depth += 1

            if len(word) == depth:
                return depth

            if cur.below_word_counts == 1:
                return depth


def solution(words):
    trie = Trie(words)
    answer = 0
    for word in words:
        answer += trie.count_typing_words(word)
    return answer