[프로그래머스] 카카오 2020년도 - 가사검색 python

https://programmers.co.kr/learn/courses/30/lessons/60060

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

 

이 문제는 이진탐색으로 해결할 수 있다 

왜냐면 fro??? 이렇게 접두사가 있으면 단어들 리스트에서 fro 가 처음 나온 인덱스랑, 마지막으로 나온 인덱스를 각각 구해서 차이를 구하면 그것이 바로 fro???에 해당하는 단어들 개수가 된다 !!

단어 탐색의 시작은 a 부터 z까지이다.

숫자 뿐만 아니라 이렇게 단어 탐색도 이진탐색을 사용할 수 있다. 여기서 신선하다고 생각 ㅋㅋ 

파이썬에는 bisect이라는 이진탐색을 쉽게 수행할 수 있도록 돕는 라이브러리가 있다 

그런데 문제제는 접두사말고도 접미사 부분이 ? 인 경우가 있다 ex) tra?? 이런 단어

이런 경우 찾으려는 단어를 거꾸로 뒤집어서 생각한다 ??art 를 또 뒤집은 단어들을 저장해놓은 reverse_array에서 찾아준다. 

string을 거꾸로 뒤집을때는 array[::-1] 이렇게 간단하게 뒤집을 수 있다 

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)]
reverse_array = [[] for _ in range(10001)]

def solution(words, queries):
    answer = []
    
    for word in words: 
        array[len(word)].append(word)
        reverse_array[len(word)].append(word[::-1])
        
    for i in range(10001): # 이진 탐색을 수행하기 위해서 각 단어 리스트 정렬 수행
        array[i].sort()
        reverse_array[i].sort()
        
    for q in queries: # 쿼리를 하나씩 처리해보자
        if q[0] != '?': # 접미사에 와일드 카드 ?????도 여기에 속한닷
            res = count_by_range(array[len(q)], q.replace('?','a'), q.replace('?', 'z'))
        else: # 접두사에 ??rodo 붙은 경우 
            res = count_by_range(reverse_array[len(q)], q[::-1].replace('?','a'), q[::-1].replace('?','z'))
        answer.append(res)
    return answer