가사 검색 (이진탐색/ binarysearch)

2020년 카카오 공채 문제중 하나인데, 시간이 꽤 걸렸고 문제를 일부분 제대로 안읽은 것을 뒤늦게 확인했습니다..

 

검색문에 추가되는 ?는 접미사 혹은 접두사로만 포함되고 반드시 하나이상 포함됩니다.

 

문제는 찾으려는 query가 주어졌을때 존재하는 단어 리스트에서 ?를 포함해 존재하는 개수를 반환하는 것입니다.

 

각 쿼리에 대해 left, right를 찾아 개수를 구해주면 쉽게 구할 수 있고 처음에는 bisect_left, right를 사용하지 않았지만 

 

사용시 보다 쉽게 풀 수 있습니다.  (사용했었는데 처음에 문자열에 적용이 안된다고 나와서 그냥 구현으로 풀려 시도했습니다. 그런데 파이썬이 역시 그럴리가 없죠)

 

주의할 부분은 접미사 접두사에 따라서 문자를 뒤집어서 확인해줘야 올바른 사전순 탐색이 가능하기 때문에 구분해서 

탐색해야합니다.

 

from bisect import bisect_left, bisect_right

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

    return right_index - left_index

array = [[] for _ in range(10001)]
reversed_array = [[] for _ in range(10001)]

def solution(words, queries):
    answer = []
    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] != '?':
            res = count_by_range(array[len(query)], query.replace('?','a'), query.replace('?','z'))
        else:
            res = count_by_range(reversed_array[len(query)], query[::-1].replace('?','a'),query[::-1].replace('?','z'))
        answer.append(res)
    return answer