title: "[프로그래머스] [3차] 자동완성 Python 파이썬 해설 (Level 4) - 이도훈"
cleanUrl: "programmers/17685"
description: "프로그래머스 Level 4 문제 [[3차] 자동완성]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

코드

import sys
sys.setrecursionlimit(10**9)

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.n = 0
        self.children = {}
    
    def finalize(self):
        self.n = 1 if self.data is not None else 0
        for char, node in self.children.items():
            self.n += node.finalize()
        
        return self.n
        
class Trie(object):
    def __init__(self):
        self.head = Node(None)
        
    def insert(self, string):
        curr_node = self.head
        
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
        
        curr_node.data = string
    
    def finalize(self):
        self.head.finalize()
        
    def search(self, string):
        depth = 0
        curr_node = self.head
        
        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
                depth += 1
                
                if curr_node.n == 1:
                    break
        
        return depth
            
def solution(words):
    trie = Trie()
    for word in words:
        trie.insert(word)
    trie.finalize()
    
    return sum(trie.search(word) for word in words)

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges