[코테] 99클럽 코테 스터디 2일차 TIL (프로그래머스 가사 검색)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/60060

풀이

처음에는 생각나는 대로 선형방식으로 풀어보려 했으나 효율성 테스트에서 시간초과가 나서 힌트를 얻어 Trie알고리즘을 사용하였다.
파이썬으로 Trie알고리즘 구현 방법은 아래 글을 참고하였다.
https://deeppago.tistory.com/11

def solution(words, queries):
    answer = []
    tries = {}
    reversed_tries = {}
    
    for word in words:
        if len(word) not in tries:
            tries[len(word)] = Trie()
            reversed_tries[len(word)] = Trie()
            
        tries[len(word)].insert(word)
        reversed_tries[len(word)].insert(word[::-1])
    
    for query in queries:
        if len(query) in tries:
            if query[0] != '?':
                trie = tries[len(query)]
                answer.append(trie.starts_with(query))
            else:
                trie = reversed_tries[len(query)]
                answer.append(trie.starts_with(query[::-1]))
        else:
            answer.append(0)
            
    return answer

class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.count = 0
        self.children = {}
        
class Trie:
    def __init__(self):
        self.head = Node(self)
        
    def insert(self, string):
        current_node = self.head
        
        for char in string:
            current_node.count += 1
            if char not in current_node.children:
                current_node.children[char] = Node(char)
                
            current_node = current_node.children[char]
            
        current_node.count += 1
        
    def starts_with(self, prefix):
        current_node = self.head
        
        for p in prefix:
            if p == '?':
                break
                
            if p in current_node.children:
                current_node = current_node.children[p]
            else:
                return 0
        
        return current_node.count

TIL

TRIE(트라이)알고리즘이란?

• 문자열을 효율적으로 저장하고 검색하기 위한 트리 기반 자료구조. 공통된 접두사를 공유하여 저장 공간을 절약하고, 문자열 검색 및 접두사 검색에서 높은 성능을 보임.
• 검색, 자동완성, 그리고 사전 관리에서 많이 사용됨.
• 문자열 삽입/검색의 시간 복잡도는 O(N)로 문자열 길이에 비례