[이진탐색] 가사검색

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 30분 + a

1. 문제 설명

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

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

2. 접근 방식

- 이진탐색을 활용해서 문제를 푼다.

- 가사 단어의 길이별로 가사 단어를 개별적으로 저장시켜 놓는다. (그렇게 되면 길이가 1인 애들부터 n인 애들끼리 각자 묶일 것이다.)

- 찾으려는 가사의 조합을 이진 탐색으로 찾기 위해서 위 가사 단어의 리스트를 정렬시킨다. 

- 이 때 찾으려는 queries의 원소들이 '???'가 앞과 뒤에 붙을 수 있는데, '???'가 앞에 붙을 경우 단어를 찾기 위해서 단어들이 뒤집힌 리스트를 하나 더 만들어 줘야 한다.(해당 부분은 코드를 보면 오히려 이해가 쉽다)

- 그래서 for문을 돌면서 각각의 쿼리들을 확인하는데, '~???'부분의 경우 '~aaa', '~zzz'로 나눠서 해당 단어들 사이의 값들만 구하면 된다. 

 

3. 코드

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:
            res = count_by_range(reverse_array[len(q)], q[::-1].replace('?','a'), q[::-1].replace('?','z'))
        answer.append(res)
    return answer

4. 코멘트

- 해당 문제도 내가 생각했던 것보다 훨씬 더 쉽게 풀었다. '?'가 붙은 단어가 등장하면서 정규식밖에 떠오르지 않았었는데, 이진탐색으로도 간결하게 풀 수 있다는 것에 놀랐다.

- 그리고 단어 리스트를 만들 때, 길이별로 따로 만드는 것이나, 단어들의 조합을 뒤집어서 저장한 별도의 리스트를 만들어서 접두에 ?가 붙는 경우도 쉽게 해결하는 기법 등은 기억해 놓을만 하다는 생각을 했다.

- 해당 문제를 풀 때 코드의 흐름은 이해하기 쉽지만, reverse된 리스트를 만들 때 단어들을 뒤집어서 넣는 것을 기억해야 한다.