2018 KAKAO BLIND RECRUITMENT- 자동완성, 파이썬

문제

---

프로그래머스 링크

• 단어가 배열로 주어지고 각 단어 검색마다 최소한으로 몇 번의 알파벳을 입력해야하는지 구한 후 더해서 리턴하는 문제

풀이

---

• 다른 방법을 활용해 풀 수도 있지만(시간초과 주의) 예전 프로그래머스 가사검색 문제를 푼 기억이 있어서 트라이 구조를 활용했다.
• 트라이 자료구조의 대표적인 활용 예가 자동완성이다.
• 통과가 되긴 했는데 잘 맞게 쓴지는 모르겠다.

코드

---

class Node():
    def __init__(self) :
        self.cnt = 0
        self.dic = {}

class Trie:
    def __init__(self):
        self.root = Node()

    def insert(self, word) :
        temp = self.root
        for w in word :
            if w not in temp.dic :
                temp.dic[w] = Node()
            temp = temp.dic[w]
            temp.cnt += 1

    def search(self, word) :
        temp = self.root
        cnt = 1
        for w in word :
            if temp.dic[w].cnt == 1:
                return cnt
            else :
                temp = temp.dic[w]
                cnt += 1
        return len(word) 

def solution(words):
    ans = 0
    t_words = Trie()
    for word in words :
        t_words.insert(word)
    for word in words :
        ans += t_words.search(word)
    return ans