[Python] Programmers 자동완성

1. 문제 링크

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

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

---

2. 문제 요약

• 검색어 자동완성으로 단어 리스트에서 찾을 때 총 몇 글자까지 입력해야 하는지 리턴한다.

 

---

3. 아이디어 정리

1. 트라이 구조 생성 
   • word_num = 0       - 현재 문자를 포함하는 단어 수
   • children = defaultdict(TrieNode)   - 자식 노드 (dict 자료형)
2. 트라이 구조에 단어들 넣기 (아래 그럼과 같이 생성) 
3. 트라이 구조로 몇 글자를 입력해야하는지 파악

수정: g의 word_num은 3입니다.

 

• 카카오 해설 을 참고하면 트라이로 풀이가 가능하다.

 

---

4. 문제 풀이

4-1. 참고한 내 풀이

from collections import defaultdict


class TrieNode:
    def __init__(self):
        self.word_num = 0      					# 현재 문자를 포함하는 단어 수 
        self.children = defaultdict(TrieNode)   # 자식 노드 (dict 자료형)

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        """
        단어 삽입
        :param word:
        :return:
        """
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node.children[char].word_num += 1   # 해당 문자를 포함하는 단어 수 + 1
            node = node.children[char]          # 다음 노드로 이동 


def solution(words):
    answer = 0
    trie = Trie()
    # 1. 트라이에 단어 삽입
    for word in words:
        trie.insert(word)

    # 2. 트라이 구조로 몇 글자를 입력해야하는지 파악
    for word in words:
        cur_node = trie.root
        for i, char in enumerate(word):
            if cur_node.children[char].word_num == 1:  # 자식에 해당 단어가 1인 경우(현재 해당 단어밖에 없는 경우)
                break
            cur_node = cur_node.children[char]   # 다음 단어로 이동
        answer += (i + 1)   # 해당 단어 입력 해야할 수 
    return answer

 

---

5. 결론

• 트라이를 이용하는 문제이다.
• 추가로 아래 카카오 문제를 풀어보자.

코딩 테스트 연습 - 가사 검색

코딩테스트 연습 - 가사 검색