2020 KAKAO BLIND RECRUITMENT 가사 검색

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

BF로 확인.. 

def solution(words, queries):
    import re
    answer = [0] * len(queries)
    for index, query in enumerate(queries):
        q = re.compile(f"^{query}$".replace("?", "."))
        for word in words:
            if q.search(word) is not None:
                answer[index] += 1
    return answer

당연히.. 

정확성  테스트
테스트 1 〉	통과 (1.79ms, 10.3MB)
테스트 2 〉	통과 (1.12ms, 10.2MB)
테스트 3 〉	통과 (1.21ms, 10.1MB)
테스트 4 〉	통과 (1.34ms, 10.1MB)
테스트 5 〉	통과 (1.40ms, 10.2MB)
테스트 6 〉	통과 (1.39ms, 10.2MB)
테스트 7 〉	통과 (16.88ms, 10.3MB)
테스트 8 〉	통과 (20.25ms, 10.2MB)
테스트 9 〉	통과 (23.47ms, 10.4MB)
테스트 10 〉	통과 (14.94ms, 10.2MB)
테스트 11 〉	통과 (14.20ms, 10.3MB)
테스트 12 〉	통과 (17.09ms, 10.3MB)
테스트 13 〉	통과 (222.45ms, 10.5MB)
테스트 14 〉	통과 (191.67ms, 10.6MB)
테스트 15 〉	통과 (225.41ms, 10.4MB)
테스트 16 〉	통과 (212.51ms, 10.5MB)
테스트 17 〉	통과 (188.19ms, 10.6MB)
테스트 18 〉	통과 (233.41ms, 10.6MB)
효율성  테스트
테스트 1 〉	실패 (시간 초과)
테스트 2 〉	실패 (시간 초과)
테스트 3 〉	실패 (시간 초과)
테스트 4 〉	통과 (499.61ms, 15.1MB)
테스트 5 〉	통과 (1274.58ms, 19.8MB)

Trie 
중간에 '?'가 나와도 검색이 되도록 재귀로 만들어 보았다. 
문제 조건에서도 재귀의 한계를 넘기는 숫자들이 보인다. 
될리가 없다.

class Trie:
    def __init__(self):
        self.root = {}

    def insert(self, word):
        current = self.root
        for letter in word:
            current.setdefault(letter, {})
            current = current[letter]
        current['*'] = word

    def search(self, word, index=0, current=None, match=0):
        if current is None:
            current = self.root
        if index == len(word):
            return match + 1 if '*' in current else match
        letter = word[index]
        if letter in current:
            match = self.search(word, index + 1, current[letter], match)
        elif letter == '?':
            for letter in current:
                match = self.search(word, index + 1, current[letter], match)
        return match


def solution(words, queries):
    import sys
    sys.setrecursionlimit(1_000_000)
    trie = Trie()
    for word in words:
        trie.insert(word)
    return [trie.search(query) for query in queries]

Trie를 글자수 별로 만들어서 같은 글자수끼리 비교한다. 

class Node:
    def __init__(self):
        self.count = 0
        self.children = {}


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

    def insert(self, word):
        current = self.root
        current.count += 1
        for letter in word:
            if letter not in current.children:
                current.children[letter] = Node()
            current = current.children[letter]
            current.count += 1
        current.children['*'] = word

    def search(self, word):
        current = self.root
        for letter in word:
            if letter not in current.children:
                return 0
            current = current.children[letter]
        return current.count


def solution(words, queries):
    tries = {}
    r_tries = {}
    for word in words:
        tries.setdefault(len(word), Trie())
        r_tries.setdefault(len(word), Trie())
        tries[len(word)].insert(word)
        r_tries[len(word)].insert(word[::-1])
    return [search_helper(tries, r_tries, query) for query in queries]


def search_helper(tries, r_tries, query):
    modified_query = query.replace('?', '')
    if len(query) not in tries:
        return 0
    if query[0] != '?':
        return tries[len(query)].search(modified_query)
    if query[-1] == '?':
        return tries[len(query)].root.count
    return r_tries[len(query)].search(modified_query[::-1])

정확성  테스트
테스트 1 〉	통과 (1.15ms, 10.5MB)
테스트 2 〉	통과 (0.25ms, 10.2MB)
테스트 3 〉	통과 (0.43ms, 10.3MB)
테스트 4 〉	통과 (0.40ms, 10.2MB)
테스트 5 〉	통과 (0.27ms, 10.3MB)
테스트 6 〉	통과 (0.46ms, 10.3MB)
테스트 7 〉	통과 (12.00ms, 12.6MB)
테스트 8 〉	통과 (5.23ms, 10.9MB)
테스트 9 〉	통과 (6.59ms, 12.6MB)
테스트 10 〉	통과 (8.23ms, 12.8MB)
테스트 11 〉	통과 (4.71ms, 10.9MB)
테스트 12 〉	통과 (6.87ms, 12.6MB)
테스트 13 〉	통과 (45.06ms, 22MB)
테스트 14 〉	통과 (26.86ms, 15.3MB)
테스트 15 〉	통과 (59.42ms, 21.4MB)
테스트 16 〉	통과 (43.93ms, 22.4MB)
테스트 17 〉	통과 (14.69ms, 14.9MB)
테스트 18 〉	통과 (36.08ms, 21.2MB)
효율성  테스트
테스트 1 〉	통과 (1253.92ms, 201MB)
테스트 2 〉	통과 (2919.92ms, 378MB)
테스트 3 〉	통과 (2742.66ms, 357MB)
테스트 4 〉	통과 (2479.01ms, 418MB)
테스트 5 〉	통과 (5375.92ms, 786MB)