[Python] Trie - 2018 카카오 : 자동완성

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

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

 

풀이

2020 카카오 가사 검색을 응용해서 풀었다.

 

remains 대신 branch를 만들어서 그 노드를 포함하는?사용하는? 단어 수를 저장했다.

1번 테스트케이스(go, gone, guild)의 경우 아래 그림처럼 트리가 만들어진다.

 

 

Trie에 단어를 삽입한다. 삽입할때 branch의 숫자를 1씩 올려준다.

그리고 다시 단어들을 탐색하는데, branch가 1이면 그 Depth 을 반환한다(코드에서 i+1). (초록색)

단어를 끝까지 탐색해도 모든 노드의 branch가 1이상이었다면(go의경우), 단어 길이를 반환한다.  (주황색)

 

class Node(object):
    def __init__(self, key):
        self.key = key
        self.children = {}
        self.branch = 0

        
class Trie(object):
    def __init__(self):
        self.root = Node(None)
    
    def insert(self, word):
        curr_node = self.root
        curr_node.branch += 1
        
        for i in range(len(word)):
            chr = word[i]
            if chr not in curr_node.children:
                curr_node.children[chr] = Node(chr)
            curr_node = curr_node.children[chr]
            curr_node.branch += 1
            if i == len(word)-1:
                curr_node.isLeaf = True
                
        
    def search_count(self, word):
        curr_node = self.root
        
        for i in range(len(word)):
            chr = word[i]
            if chr in curr_node.children:
                curr_node = curr_node.children[chr]
                if curr_node.branch == 1:
                    return i+1
        return len(word)
                    
            

def solution(words):
    t = Trie()
    for word in words:
        t.insert(word)
   
    answer = 0 
    for word in words:
        answer += t.search_count(word)
    return answer