[python] 프로그래머스 60060번 : 가사검색 (bisect)

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

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

 

1. 정답인 코드 

from bisect import bisect_left, bisect_right

def count_by_value(a, left_value, right_value):
    left_idx = bisect_left(a, left_value)
    right_idx = bisect_right(a, right_value)
    
    return right_idx - left_idx
    
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_value(array[len(q)], q.replace('?','a'), q.replace('?','z'))
        else:
            result = count_by_value(reversed_array[len(q)], q[::-1].replace('?','a'), q[::-1].replace('?','z'))
            
        answer.append(result)
    return answer

 

 

이것이 코딩테스트다 답안을 확인하여 해당 코드를 구현할 수 있었다.

궁금한 점은 '????o' 와 같은 문자열을 처리해야 하는 경우, 왜 뒤집힌 단어에 대한 리스트인 reversedArr를 생성해야만 하는가였다.

그 이유는 bisect를 활용하여 포함된 리스트에서 해당 범위의 문자열의 개수를 파악하기 위해서였다. 

 

예를 들어 '????o'라는 문자열이 query로 주어진 경우, 해당 문자는 길이가 5이므로

array[5]에 저장되어 있는 리스트 원소에 대해 이 키워드의 포함 여부를 파악한다.

words 내 리스트를 정렬하면 

[[], [], [], [], [], ['frame', 'frodo', 'front', 'frost', 'kakao'], ['frozen'], []]

 

와 같이 맨 앞글자부터 알파벳순으로 데이터가 정렬된 것을 확인할 수 있다.

이때 '????o'를 포함하는 단어는 2개뿐이지만 bisect로 구현된 count_by_value() 함수를 처리할 때   

left_idx는 0, right_idx는 5을 가리키게 된다. 따라서 해당 데이터를 포함하는 단어의 개수로 5가 리턴되는데 이러한 문제가 발생하는 이유는 bisect 구현시 정렬된 데이터에 대해서만 탐색이 가능하기 때문이다. 

 

즉, 다시 말해 '????o'와 같은 query는 words 리스트의 단어를 뒤집어서 정렬한 리스트(reversedArr)에 대해서 처리해야만 정렬된 데이터로서 정상 동작하는 것을 알 수 있다.