[프로그래머스] 가사 검색 (이분탐색, 카카오, bisect)

https://programmers.co.kr/learn/courses/30/lessons/60060?language=python3

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

# 이분탐색으로 해결. 추후 Trie 자료구조로 요망
from bisect import bisect_left, bisect_right
 
 
def solution(words, queries):
    answer = list()
    forward = [list() for _ in range(10001)]
    backward = [list() for _ in range(10001)]
 
    for word in words:
        forward[len(word)].append(word)
        backward[len(word)].append(word[::-1])
    for i in range(10001):
        forward[i].sort()
        backward[i].sort()
 
    for query in queries:
        if query[0] != '?':
            l = bisect_left(forward[len(query)], query.replace('?', 'a'))
            r = bisect_right(forward[len(query)], query.replace('?', 'z'))
            answer.append(r - l)
        else:
            l = bisect_left(backward[len(query)], query[::-1].replace('?', 'a'))
            r = bisect_right(backward[len(query)], query[::-1].replace('?', 'z'))
            answer.append(r - l)
    return answer

이분탐색으로 해결했다. Trie 자료구조를 이용해서 해결할 수 있지만, 그 방법은 추후에 2회차 풀이 때 시도하려고 한다.

bisect 라이브러리를 사용했는데, bisect_left와 right는 "정렬이 되어있다는 가정 하에" 삽입을 한다면 왼쪽, 오른쪽을 기준으로 어디에 삽입될지 찾는 함수이다. 이 함수가 이분탐색의 역할을 한다.