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

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

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

 

저번에 Trie 자료구조를 유튜브를 통해서 배운 적이 있는데 문제를 보고 Trie 를 이용해야겠다고 생각이 났다.

문자열을 한 문자씩 정의하여 dictionary 에 담아서 dictionary[] 의 길이를 가지고 몇 번의 입력으로 자동완성이 되는지를 판별해주면 된다.

 

예를 들어, dictionary['g'] 의 길이가 2개 이상이라면 'g' 를 입력했을 때 2개의 단어를 추천해주므로 자동완성을 할 수 가 없다. 또한 'go' 와 'gone' 에서 dictionary['g']['o'] 의 길이는 1이나 'go' 를 입력했을 때 'go', 'gone' 을 추천해주므로 단어가 끝날 때 '!' 를 추가하여 구분해준다.

 

class Trie:
    dictionary = {}
    
    def insert(self, string):
        current_dic = self.dictionary
        
        for i in string:
            if i not in current_dic:
                current_dic[i] = {}
            
            current_dic = current_dic[i]
        
        current_dic['!'] = '!'
        
    def check(self, string):
        current_dic = self.dictionary
        count = 0
        
        for i in string:
            if len(current_dic[i]) == 1:
                count += 1
            else:
                count = 0
                
            current_dic = current_dic[i]
        
        return len(string) if count == 0 else len(string) - count + 1
        
def solution(words):
    answer = 0
    T = Trie()
    
    for i in words:
        T.insert(i)
    
    for i in words:
        answer += T.check(i)

    return answer

print(solution(['go', 'gone', 'guild'])) # 7

 

참고 : https://www.youtube.com/watch?v=7e1b70dTAd4