카카오 2018 자동완성

dasd412·2022년 7월 24일

코딩 테스트

목록 보기

58/71

문제 설명

포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g 만 입력해도 go를 추천해주므로 o를 입력할 필요가 없어진다! 단, 학습에 사용된 단어들 중 앞부분이 같은 경우에는 어쩔 수 없이 다른 문자가 나올 때까지 입력을 해야 한다.
효과가 얼마나 좋을지 알고 싶은 라이언은 학습된 단어들을 찾을 때 몇 글자를 입력해야 하는지 궁금해졌다.

라이언을 도와 위와 같이 문자열이 입력으로 주어지면 학습을 시킨 후, 학습된 단어들을 순서대로 찾을 때 몇 개의 문자를 입력하면 되는지 계산하는 프로그램을 만들어보자.

입력 조건

학습과 검색에 사용될 중복 없는 단어 N개가 주어진다.
모든 단어는 알파벳 소문자로 구성되며 단어의 수 N과 단어들의 길이의 총합 L의 범위는 다음과 같다.

2 <= N <= 100,000
2 <= L <= 1,000,000

출력 조건

단어를 찾을 때 입력해야 할 총 문자수를 리턴한다.

전체 코드

from collections import deque

class Node:
    def __init__(self,key):
        self.key=key
        self.data=None
        self.children=dict()

class Trie:
    def __init__(self):
        self.root=Node(None)
    
    def insert(self,string:str):
        current=self.root
        
        for char in string:
            if char not in current.children:
                current.children[char]=Node(char)
                
            current=current.children[char]
        
        current.data=string
    
    def calculate_input_length(self,string:str)->int:
        current=self.root
        # 방문한 노드를 추적하는 스택
        previous_trace=deque()
        
        # 찾고자 하는 단어가 있는 곳 (data로 기재되어 있는 곳)까지 이동한다.
        for char in string:
            previous_trace.append(current)
            current=current.children[char]
        
        # 2-1.'go'와 'gone'에서 다른 단어의 접두어가 되는'go'의 경우 길이 그대로인 2를 리턴해야 한다.
        if len(current.children):
            return len(current.data)
        # 2-2. 다른 단어의 접두어가 되지 않을 경우에는 거슬러 올라간다.
        else:
            trace_count=0
            
            while previous_trace:
                poped=previous_trace.pop()
                # 2-2-1.접두어가 될 수 있는 단어를 발견한 경우 
                if poped.data!=None:
                    break
                # 2-2-2. 또다른 자식으로 분기가 나뉘는 경우
                elif len(poped.children)>1:
                    break
                
                trace_count+=1
            
            return len(string)-trace_count

def solution(words):
    answer = 0
    
    # 1. 트라이를 구성한 후, 단어들을 트라이에 집어 넣는다. 트라이는 접두어 검색에 좋다.
    trie=Trie()
    for word in words:
        trie.insert(word)
    
    # 2. 
    for word in words:
        answer+=trie.calculate_input_length(word)
        
    return answer