[프로그래머스] 자동완성 (트라이)

https://school.programmers.co.kr/learn/courses/30/lessons/17685?language=python3 

프로그래머스

 

분석

학습된 단어들이 아래와 같을 때
- go
- gone
- guild

go를 찾을 때 go를 모두 입력해야 한다.
gone을 찾을 때 gon 까지 입력해야 한다. (gon이 입력되기 전까지는 go 인지 gone인지 확신할 수 없다.)
guild를 찾을 때는 gu 까지만 입력하면 guild가 완성된다.

이 경우 총 입력해야 할 문자의 수는 7이다.

 

 2023.06.05 - [BOJ/Tree] - [14425] 문자열 집합 (트라이, Trie) 

[14425] 문자열 집합 (트라이, Trie)

 

풀이

# 노드 클래스 생성
class Node(object):
    def __init__(self, wordCnt):
        self.wordCnt=0 # 만들 수 있는 단어수
        self.childNode={}  # 자식노드

class Trie(object):
    def __init__(self):
        self.parent=Node(None)  # 부모노드 저장 변수

    # 문자 삽입
    def insert(self, string):
        nowNode=self.parent
        for char in string:
            nowNode.wordCnt+=1
            if char not in nowNode.childNode:
                nowNode.childNode[char]=Node(char)
            nowNode=nowNode.childNode[char]  # 자식노드로 이동
        nowNode.wordCnt+=1
        
    # 문자열 존재하는지 탐색
    def search(self, string):
        nowNode=self.parent
        for char in string:
            if char in nowNode.childNode:
                nowNode=nowNode.childNode[char]
            else:
                return False
        if nowNode.wordCnt==1:
            return True
        else:
            return False

def solution(words):
    answer = 0

    myTrie=Trie()  # Trie 생성
    for x in words: 
        myTrie.insert(x)   # 단어 삽입
        
    for word in words:
        already_find=False
        for i in range(1, len(word)+1):
            if myTrie.search(word[:i]):
                answer+=len(word[:i])
                already_find=True
                break
                
        if not already_find:
            answer+=len(word)
            
    return answer