30_가사 검색

 

프로그래머스

 

이진 탐색 문제.

아무리 생각해봐도 어떻게 이진 탐색을 돌아야 될지 모르겠어서 풀이를 봤다.

 

---

풀이 코드

# 가사 검색
from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(arr, left_value, right_value):
    right_index = bisect_right(arr, right_value)
    left_index = bisect_left(arr, 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] != '?': # 접미사에 와일드카드가 붙은 경우
            res = count_by_range(array[len(q)], q.replace('?', 'a'), q.replace('?', 'z'))
        else: # 접두사에 와일드카드가 붙은 경우
            res = count_by_range(reversed_array[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?','z'))
            
        answer.append(res)
        
    return answer

 

 

문제의 핵심 아이디어는 이렇다.

 

주어진 word의 길이별로 따로 저장하는 리스트를 만든다.

그리고 각 query마다 와일드카드(?)에 해당하는 범위의 문자의 개수를 세주면 된다.

이 부분을 어떻게 해야할 지 도저히 몰랐어서 못 풀었는데,

만약 fro?? 인 경우, froaa ~ frozz까지 세면 되므로 replace함수와 count_by_range함수를 통해 해결하면 된다.

 

진짜 이렇게 구현할 수 있다니, 이코테 책을 보면서 제일 놀란 풀이였다.

이런 문제해결력은 어떻게 키우는 걸까?

문제를 많이 풀다보면 생길까?