[알고리즘] 가사 검색

📌 문제

가사 검색

📌 문제 해결 hint

1. 각 단어를 길이에 따라 나눈다.
2. 리스트를 정렬한다.
3. 이진탐색으로 시작되는 단어("fro??" 보다 크거나 같은 단어)의 위치부터
   마지막 단어("frozz"보다 작거나 같은 단어)의 위치의 차이를 계산하여 개수를 구한다.
4. 단어중에 ???로 시작하는 단어가 있어 뒤집은 단어를 담고 있는 리스트를 별도로 만든다.
5. 뒤집힌 단어 리스트를 대상으로 위와 같은 이진 탐색을 수행하면 된다.

📌 bisect 함수란?

from bisect import bisect_right, bisect_left

a = [1,2,3,4,4,8]
x = 4

print(bisect_left(a,x)) 
>> 3
print(bisect_right(a,x)) 
>> 5

📌 solution

from bisect import bisect_left, bisect_right


def count_by_range(a, left_value, right_value):
    right_value = bisect_right(a, right_value)
    left_value = bisect_left(a, left_value)

    return right_value - left_value


def solution(words, queries):
    answer = []

    # 1. 각각의 리스트를 길이에 따라 나눈다.
    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])

    # 2. 리스트를 정렬한다.

    for i in range(10001):
        array[i].sort()
        reversed_array.sort()

    # 3. 이진탐색으로 시작되는 단어부터 마지막 단어의 위치를 찾고 위치의 차이를 계산

    for query in queries:
        if query[0] != '?':
            res = count_by_range(array[len(query)], query.replace('?', 'a'), query.replace('?', 'z'))
        else:
            res = count_by_range(reversed_array[len(query)], query.replace('?', 'a'), query.replace('?', 'z'))

        answer.append(res)

        return answer