[프로그래머스] - 자동완성

class Trie():
    head = [0, dict()]

    def add(self, word):
        current = self.head
        current[0] += 1
        for x in word:
            if x not in current[1]:
                current[1][x] = [0, dict()]
            current = current[1][x]
            current[0] += 1

    def check(self, word):
        current = self.head
        result = 0
        for x in word:
            if current[0] == 1:
                return result
            result += 1
            current = current[1][x]
        return result


def solution(words):
    answer = 0
    T = Trie()
    for word in words:
        T.add(word)
    for word in words:
        answer += T.check(word)
    return answer

 

2018 카카오 블라인드 3차 - 5번

1. Trie 클래스 정의

    - head : [하위노드수, dic()]

    - add : Trie자료구조에 문자열을 추가하는 함수 (추가할 때마다 head와 같은 구조를 만들어주고 하위노드수 증가)

    - check : Trie자료구조를 이용하여 해당함수의 입력단어를 반환받음 (하위노드가 자기자신 뿐이면 바로 resturn)

2. words를 전부 add를 해준다

3. words를 전부 check를 해준다

4. return answer

 

Trie자료구조를 이용해서 푸는 문제

머리 구석에 있던 것을 생각해서 끄집어 내느라 고생했다