2020 카카오 블라인드 채용 - 가사 검색

[문제]

프로그래머스

[첫번째 시도] 실패 - 정확성O/ 효율성X

def solution(words, queries):
    answer = []
    for query in queries:
        count = 0
        for word in words:
            if len(query) != len(word):
                continue
            for i in range(len(query)):
                if query[i] != '?' and query[i] != word[i]:
                    break
                if i == len(query)-1:
                    count += 1
        answer.append(count)
    return answer

문제점: 문제의 '검색 키워드 제한사항'을 충분히 숙지하지 않고 접근했음.

 

[두번째 시도] 실패 - 정확성O/ 효율성X

def solution2(words, queries):
    answer = []
    reversed_words = ["".join(reversed(word)) for word in words]
    for query in queries:
        if query[0] == '?':
            reversed_query = "".join(reversed(query))
            lower_bound = reversed_query.replace('?', 'a')
            upper_bound = reversed_query.replace('?', 'z')
            count = 0
            for word in reversed_words:
                if len(word) != len(query):
                    continue
                if word >= lower_bound and word <= upper_bound:
                    count += 1
        else:
            lower_bound = query.replace('?', 'a')
            upper_bound = query.replace('?', 'z')
            count = 0
            for word in words:
                if len(word) != len(query):
                    continue
                if word >= lower_bound and word <= upper_bound:
                    count += 1
        answer.append(count)
    return answer

[세번째 시도] 성공 - 정확성O/ 효율성O

from collections import defaultdict
from bisect import bisect_left, bisect_right

def solution(words, queries):
    answer = []
    word_list = defaultdict(list)
    rev_word_list = defaultdict(list)
    for word in words:
        word_list[len(word)].append(word)
        rev_word_list[len(word)].append(word[::-1])
    for key in word_list.keys():
        word_list[key].sort()
        rev_word_list[key].sort()
    for query in queries:
        start = query.replace('?', 'a')
        end = query.replace('?', 'z')
        if query[0] == '?':
            lst = rev_word_list[len(query)]
            s = bisect_left(lst, start[::-1])
            e = bisect_right(lst, end[::-1])
        else:
            lst = word_list[len(query)]
            s = bisect_left(lst, start)
            e = bisect_right(lst, end)
        answer.append(e-s)
    return answer


words = ["frodo", "front", "frost", "frozen", "frame", "kakao"]
queries = ["fro??", "????o", "fr???", "fro???", "pro?"]
print(solution(words, queries))