풀기 전 생각 정리

1) words와 queries의 범위를 고려했을 때 2중 for을 돌리면 시간 초과가 난다.

2) 이진 탐색을 어느 부분에서 사용해야 하는가?
querie의 단어 길이 탐색에서 한번, 단어 찾을 때 두번 사용하기로 생각을 정리했다.
(두번 탐색을 쓰려는 생각이 별로 좋지 못했다) => words.sort(key=lambda x : (len(x), x))로 정렬해서 이진 탐색을 두번 사용하려 했지만 결국 이차원 배열을 통해 길이마다 바로 접근할 수 있는 배열을 구현해 놓는 것이 더 좋은 방법이었다.

코드

from bisect import bisect_left, bisect_right

def solution(words, queries):
    answer = []
    lens = [[] for _ in range(10001)]
    r_lens = [[] for _  in range(10001)]

    for word in words:
        lens[len(word)].append(word)
        r_lens[len(word)].append(word[::-1])

    for i in range(10001):
        lens[i].sort()
        r_lens[i].sort()

    for querie in queries:

        querie_len = len(querie)

        if querie[-1] == "?": # 뒤쪽으로 ?가 붙은 경우
            start = bisect_left(lens[querie_len], querie.replace("?", "a"))
            end = bisect_right(lens[querie_len], querie.replace("?","z"))

        else:
            t_querie = querie[::-1]
            start = bisect_left(r_lens[querie_len], t_querie.replace("?", "a"))
            end = bisect_right(r_lens[querie_len], t_querie.replace("?", "z"))

        answer.append(end-start)
    return answer

리뷰

처음 코드를 구현할 때 replace를 통해 search를 한다고까진 구상했지만 접두어로 ?가 붙는 경우를 처리하지 못해 결국 코드를 다시 구상했다. 너무나 당연하게 단어들을 뒤집으면 동일한 알고리즘으로 구현할 수 있다는 것을 알고 조금 허탈하게 코드를 마저 완성했다.

from bisect import bisect_left, bisect_right
bisect_left(list, 원하는것)의 개념을 다시 확인해 볼 수 있는 문제였기에 좋았다.