[프로그래머스] 가사 검색, Python3

문제는 여기!

해당 검색키워드가 접두사 혹은 접미사에 '?'가 붙어있다. 검색키워드에 맞는 가사 단어 갯수를 리턴하는 문제이다. '?'를 어떻게 처리하는지가 관건인 문제!

제한사항 및 주의사항

가사 단어의 갯수는 1 <= 100,000

각 가사 단어의 길이는 1 <= 10,000

검색 키워드 단어의 갯수는 2 <= 100,000

검색 키워드 단어의 길이도 가사 단어와 일치, 1 <= 10,000

'?'(와일드카드)는 하나 이상 포함되어 있으며 접두사 혹은 접미사에 포함되어 있다.

풀이전략

우선 가사 단어들을 단어의 길이 별로 배열에 넣고 정렬하자. 문제에서 검색 키워드 단어의 길이도 가사 단어의 길이와 일치해야 한다. 가사 단어의 길이는 10,000까지 이므로 10,001 크기의 배열을 선언해서 단어들을 넣어주자.

len_words[ 가사 단어의 길이 ] = 가사 단어

그리고 가사 단어를 거꾸로해서 길이 별로 배열에 넣고 정렬하는 것도 해야한다. 그 이유는 뒤에서 설명하겠다.

이후, 검색 키워드를 하나씩 보면서 검색 키워드에 맞는 가사 단어를 찾을 것이다. 해당 검색 키워드 길이와 똑같은 배열에 접근해서 단어의 갯수를 찾아 answer 배열에 담으면 된다.

이때 접두사에 ?가 있는지, 접미사에 ?가 있는지에 따라 다르게 탐색해야하는데, 접두사에 ?가 붙은 경우를 대비해 앞에서 가사 단어를 거꾸로 해서 저장한 배열을 선언한 것이다. 그림으로 하나씩 보면서 해보자. 문제에 주어진 예제를 그대로 활용하겠다.

위에 사각형 안에 단어들을 밑에 단어들을 거꾸로 해서 정렬했다. '????o'와 일치하는 키워드를 찾을 때, '????o'도 'o????'로 거꾸로 해서 찾자.

여기서 bisect 모듈을 활용해 찾으려는 단어가 배열의 어느 순서에 들어가야 하는지 리턴되는 인덱스를 갖고 단어 수를 셀 것이다.

와일드카드 모두 a로 치환하면 bisect_left 메서드로 인해 'oaaaa(o????)'는 'emarf', 'oakak' 사이의 인덱스에 위치하므로 1을 반환한다. 그리고 와일드카드 모두 z로 치환하면 bisect_right 메서드로 인해 'ozzzz(o????)'는 'odorf'와 'tnorf'의 사이 인덱스에 위치하므로 3을 반환한다.

bisect_right의 인덱스에서 bisect_left 인덱스를 빼면 2가 되며, '????o'의 단어와 일치하는 가사 단어의 갯수는 2개임을 확인할 수 있다. 이와 같은 방식으로 풀이했으며, 밑에 코드를 작성해두었다.

from bisect import bisect_left, bisect_right


def solution(words, queries):
    answer = []
    len_words = [[] for _ in range(10001)]
    reverse_len_words = [[] for _ in range(10001)]
    for w in words:
        len_words[len(w)].append(w)
        reverse_len_words[len(w)].append(w[::-1])

    for i in range(10001):
        len_words[i].sort()
        reverse_len_words[i].sort()

    for i in range(len(queries)):
        n = len(queries[i])
        if queries[i][0] != "?":
            find_left_index_query = queries[i].replace("?", "a")
            find_right_index_query = queries[i].replace("?", "z")
            answer.append(
                bisect_right(len_words[n], find_right_index_query)
                - bisect_left(len_words[n], find_left_index_query)
            )
        else:
            find_left_index_query = queries[i][::-1].replace("?", "a")
            find_right_index_query = queries[i][::-1].replace("?", "z")
            answer.append(
                bisect_right(reverse_len_words[n], find_right_index_query)
                - bisect_left(reverse_len_words[n], find_left_index_query)
            )

    return answer