[카카오2020] 가사 검색 in Python

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

코딩테스트 연습 - 가사 검색

 

<풀이>

이진탐색 라이브러리인 bisect의 bisect_left와 bisect_right을 이용하여 같은 길이의 가사들 중에서 쿼리를 포함하는 단어의 첫 인덱스, 마지막 인덱스 차이를 구한다 !

이진 탐색 라이브러리 bisect 정리 : https://sinclairstudio.tistory.com/85

python bisect, bisect_left, bisect_right

 

from bisect import bisect_left, bisect_right

def count_by_range(word, left_value, right_value):
    
    right_index = bisect_right(word, right_value)
    left_index = bisect_left(word, left_value)
    return right_index - left_index

def solution(words, queries):
    answer = []
    
    array = [[] for _ in range(10001)]
    reversed_array = [[] for _ in range(10001)]
    
    for word in words:
        array[len(word)].append(word)
        reversed_array[len(word)].append(word[::-1])
    
    for i in range(10001):
        array[i].sort()
        reversed_array[i].sort()
    
    for query in queries:
        if query[0] != '?': # fro??? 같은 경우 
            count = count_by_range(array[len(query)], query.replace('?','a'), query.replace('?','z'))
            answer.append(count)
        else:
            count = count_by_range(reversed_array[len(query)], query[::-1].replace('?','a'), query[::-1].replace('?','z'))
            answer.append(count)
     
    return answer