[Binary Search] kakao 60060 가사 검색

 

🎈 kakao 60060 가사 검색

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

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

 

❗ 문제의 핵심, 풀이 과정

• '?'는 글자 하나를 의미한다.

=> 예를 들어, "fro??" 는 길이가 5인 단어이며, 길이가 5인 단어리스트에서 찾는 것이 효율적이다.

=> 모든 단어들이 담긴 배열 words에서 각 단어들을 길이별로 구분하여 저장한다.

 

• 와일드카드 문자인 '?'는 반드시 하나 이상 포함되어있으며, 검색 키워드의 접두사 아니면 접미사이다.

=> 접두사인 경우 단어를 뒤집어서 저장한다. -> reversed_arr 이용

 

• 모든 단어들이 담긴 배열 words에서 키워드가 담긴 배열 queries의 키워드 별로 매치된 단어가 몇 개인지를 찾아야 한다. 

=> 각 쿼리를 확인하며 키워드에 매치되는 단어가 몇 개인지 센다.

     - bisect_left, bisect_right를 이용한 count_by_range를 이용한다.

 

✅ 전체 코드

import bisect

# 값이 [left_val, right_val] 데이터의 개수를 반환하는 함수
def count_by_range(a, left_val, right_val):
    right_index = bisect.bisect_right(a, right_val)
    left_index = bisect.bisect_left(a, left_val)
    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 x in queries:
        if x[0] != '?':
            # ___a ~ ___z 까지의 단어 갯수를 찾음
            result = count_by_range(arr[len(x)], x.replace('?', 'a'), x.replace('?', 'z'))
        else:
            result = count_by_range(reversed_arr[len(x)], x[::-1].replace('?', 'a'), x[::-1].replace('?', 'z'))

        answer.append(result)

    return answer

 

정수 이진 탐색 문제만 접하다 문자로 된 것을 하려니 문자열 처리나 범위 부분에서 어떻게 해야할 지 감이 잡히지 않았다. 파이썬 문자열 처리 방법을 정리할 필요가 있는 것 같고, 문자열과 관련된 문제를 더 풀어봐야겠다.

 

* 이것이 코딩테스트다 with 파이썬 - 나동빈