[카카오] 가사 검색

출처:: programmers.co.kr/learn/courses/30/lessons/60060

분류:: 이분탐색

 

1. 문제 이해 및 해결과정

- bisect이용  1. words의 길이를 세서 길이 별로 배열을 따로 저장한다. 2. 접두사를 해결하기 위해  words를 뒤집은 배열을 저장한다 3. 정렬 4. count_by_range()함수를 이용해서 접미사에 ? 있으면 a부터 z까지의 범위 내의 개수를 찾는다   ex) fro?? 라면 froaa보다 크거나 같고 frozz보다 작거나 같은 단어의 개수를 센다 5. 접두사에 ? 인경우를 처리하기 위해 reversed를 이용한다 6. 개수 저장한다

 

2. 풀이방법

  1. python 이분탐색

from bisect import bisect_left,bisect_right #정렬된배열에서 특정 원소를 찾을 때

#값이 [left_value,right_value] 인 데이터의 개수를 반환하는 함수 
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

arr = [[] for _ in range(10001)]
reversed_arr = [[] for _ in range(10001)]

def solution(words, queries):
    answer = []
    for word in words: 
        arr[len(word)].append(word)
        reversed_arr[len(word)].append(word[::-1]) #뒤집어서 삽입
        
    for i in range(10001): #정렬
        arr[i].sort()
        reversed_arr[i].sort()
    
    for q in queries:
        if q[0] != '?': #접두사에 와일드 카드 
            res=count_by_range(arr[len(q)],q.replace('?','a'),q.replace('?','z'))
        else:
            res=count_by_range(reversed_arr[len(q)],q[::-1].replace('?','a'),q[::-1].replace('?','z'))
        answer.append(res)
    return answer

 

3. 오답원인

 

4. 알게된 점