Programmers. 가사 검색

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 가사 검색

문제 풀이

Trie 사용은 알고 있어서 정확성은 모두 통과했으나 효율성에서 통과하지 못했다. 보아하니 정규식의 길이가 정확히 매칭되어야 하므로 가능한 모든 길이에 trie를 생성하고 길이 별로 쿼리해서 탐색을 줄여야 했다.

• 가능한 단어 길이만큼의 trie, 역순 단어를 저장할 trie 배열 선언
• 각 단어에 대해 단어 길이에 해당하는 trie에 단어, 역순 단어 삽입
• 삽입 시 count를 1 올려 이후 ?가 왔을 때 현재 단어를 거쳐간 단어의 개수를 리턴

python 코드

import sys
sys.setrecursionlimit(100001)
class Trie:
    def __init__(self):
        self.count = 0
        self.child = {}

    def insert(self, word, idx):
        self.count += 1
        if idx == len(word):
            return
        if word[idx] not in self.child:
            self.child[word[idx]] = Trie()
        self.child[word[idx]].insert(word, idx + 1)
    def search(self, word, idx):
        if idx == len(word):
            return self.count
        if word[idx] not in self.child:
            return 0
        return self.child[word[idx]].search(word, idx + 1)

def solution(words, queries):
    trie = [Trie() for n in range(10002)]
    rev_trie = [Trie() for n in range(10002)]
    for word in words:
        trie[len(word)].insert(word, 0)
        rev_trie[len(word)].insert(word[::-1], 0)
    answer = []
    for q in queries:
        x = q.replace("?", "")
        if q[0] == "?":
            answer.append(rev_trie[len(q)].search(x[::-1], 0))
        else:
            answer.append(trie[len(q)].search(x, 0))
    return answer

여기서 참고할 점은 defaultdict를 쓰면 시간이 지연되어 효율성 일부를 맞출 수 없다. 따라서 기본 dict 자료형을 사용해야 한다.