가사 검색 - 2020 카카오 공채 (python)

프로그래머스, 2020 카카오 공채 코딩테스트 기출 - 가사 검색 LV4
https://programmers.co.kr/learn/courses/30/lessons/60060
효율성 테스트 뚫기가 관건인 문제, 이분 탐색이용, bisect 모듈 사용

👀 깃헙 소스

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

입출력 예

words
["frodo", "front", "frost", "frozen", "frame", "kakao"]
queries
["fro??", "????o", "fr???", "fro???", "pro?"]
result
[3, 2, 4, 1, 0]

"fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
"????o"는 "frodo", "kakao"에 매치되므로 2입니다.
"fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
"fro???"는 "frozen"에 매치되므로 1입니다.
"pro?"는 매치되는 가사 단어가 없으므로 0 입니다.

솔루션
각 길이별로 단어를 정렬한 sorted cand 와 sortedreverse_cands 딕셔너리를 만든다. 이때 접두사일 때는 뒤집어서, 접미사일때는 그대로 단어를 저장한다.

# sorted cand
5: {['frame', 'frodo', 'front', 'frost', 'kakao'], 6: ['frozen']}
#  sortedreverse_cands
{5: ['emarf', 'oakak', 'odorf', 'tnorf', 'tsorf'], 6: ['nezorf']}

쿼리랑 같은 단어들을 탐색하는데, 접두사인지 접미사인지에 따라
?를 a와 z로 바꿔준후 그 사이에 있는 단어들을 탐색한다

# bisect_left, bisect_right
froaa ~ frozz
['frame', **'frodo', 'front', 'frost'**, 'kakao']
oaaaa ~ ozzzz
['emarf', **'oakak', 'odorf',** 'tnorf', 'tsorf']
fraaa ~ frzzz
[**'frame', 'frodo', 'front', 'frost',** 'kakao']

코드
시간복잡도 : O(NlogN)

# 파이썬
from collections import defaultdict
from bisect import bisect_left, bisect_right

def count_by_lange(lst, start, end):
    return bisect_right(lst, end) - bisect_left(lst, start)

def solution(words, queries):
    answer = []
    cands = defaultdict(list)
    reverse_cands = defaultdict(list)
    # 길이별 저장
    for word in words:
        cands[len(word)].append(word)
        reverse_cands[len(word)].append(word[::-1])
    # 정렬 O(NlogN)
    for cand in cands.values():
        cand.sort()
    for cand in reverse_cands.values():
        cand.sort()
    # 탐색 O(N * logM)
    for query in queries:
        if query[0] == '?': # 와일드카드 접두사 일 때
            lst = reverse_cands[len(query)]
            start, end = query[::-1].replace('?','a'), query[::-1].replace('?','z')
        else: # 와일드카드 접미사 일 때
            lst = cands[len(query)]
            start, end = query.replace('?','a'), query.replace('?','z')
        answer.append(count_by_lange(lst, start, end))

    return answer

효율성 실패 1차 코드
시간복잡도 : O(MN)

# 파이썬
import re

def solution(words, queries):
    answer = []
    for query in queries:
        query = query.replace('?','.')
        count = 0
        for word in words:
            if re.findall(query, word) and len(query) == len(word):
                count+=1
        answer.append(count)
    return answer