[알고리즘] 가사검색 - 이진탐색

✏️ 문제 링크:

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

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

소스코드와 아이디어는 '이것이 취업을 위한 코딩테스트다 with 파이썬' 동빈나 저자님에서 따온 것임을 알립니다!

---

✏️ 소스 코드:

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 q in queries:
        if q[0] != '?':
            result = count_by_range(array[len(q)],q.replace('?','a'), q.replace('?','z'))
        else:
            result = count_by_range(reversed_array[len(q)],q[::-1].replace('?','a'), q[::-1].replace('?','z'))
        
        answer.append(result)
        
    return answer

---

✏️ 설명:

중요한 아이디어는 다음과 같다

- 단어 길이에 따라 각각 배열에 따로 집어 넣기
- bisect 라이브러리를 활용하여 키워드가 담긴 단어의 갯수 구하기
- 접두사에 ?가 있는 것과 접미사에 ?가 있는 것을 따로 계산

만약 'fro??'가 queries로 주어진다면

접미사가 ?이고 ,단어의 길이가 5개인 배열에서 , 'froaa' ~ 'frozz' 사이에 있는 단어의 갯수를 찾아내는 것이다.

 

만약 '????o'가 queries로 주어진다면

접두사가 ?이고, 단어의 길이가 5개인 배열에서, 'oaaaa' ~ 'ozzzz' 사이에 있는 단어의 갯수를 찾아내는 것이다.

 

나도 같은 아이디어를 생각해냈지만..... 정돈하지 못했던 것 같다.

반복해보잣