[Programmers] 가사 검색

[Programmers] Q60060 가사 검색

Question

Language: Python

주어진 list에 대해서 특정 쿼리들을 요청했을 때 해당 쿼리에 대해 매칭되는 문자열의 개수를 구하는 문제이다.

예제와 같이 [“frodo”, “front”, “frost”, “frozen”, “frame”, “kakao”]이 있을때, “fro??”에 대한 쿼리에 대응하는 문자열의 개수는 “frodo”,”front”,”frost” 총 3개이다.

우선 쿼리에 대한 분석을 해볼 필요가 있다.

“fro??”에서 파생될 수 있는 문자열의 종류는 “froaa”~”frozz”사이의 모든 문자열이다.

그러면 만약 이 경계선상에 있는 문자열에 대해 리스트에 넣고, 이분탐색을 진행하면 어떻게 될까?

“froaa”는 “frodo”앞에, “frozz”는 “frost” 뒤에 위치하게 된다. 이렇게 되면 “froaa”의 index 값과 “frozz”의 index값을 이용해서 그 사이에 있는 문자열의 개수를 구해 낼 수 있다.

하지만 ?가 앞에는 쿼리에 대해서는 어떻게 해야될까?

만약 위와 같이 동일하게 적용해버리면, 올바르지 못한 결과가 나오게 된다.(사전순으로 정리하게 되면 항상 a가 맨앞에 오게 되고, z는 맨뒤에 오기 때문에, 맨 앞에 ?에 a가 오면 항상 맨앞에 가고, ?에 z가 오면 항상 뒤에 가기 때문에)

그래서 ? 에대한 쿼리를 해결하기 위해 문자열의 역전 시켜서 생각한다.

query가 ????o 라면 –> o???? 라고 생각한다. 또한 list에 있는 문자열들도 역전시킨다. [‘odorf’, ‘tnorf’, ‘tsorf’, ‘nezorf’, ‘emarf’, ‘oakak’]를 하고 이를 다시 정렬한 다음 [‘emarf’, ‘nezorf’, ‘oakak’, ‘odorf’, ‘tnorf’, ‘tsorf’] oaaaa,ozzzz를 넣고 해당 index들의 차이를 구하면 된다.

Solution

from bisect import bisect_left, bisect_right

def count_by_range(a,left_value,right_value):
    left_index=bisect_left(a,left_value)
    right_index=bisect_right(a,right_value)
    return right_index-left_index

def solution(words, queries):
    answer = []
    word_array=[[] for _ in range(10001)]
    reversed_word_array=[[] for _ in range(10001)]
    
    for word in words:
        word_array[len(word)].append(word)
        reversed_word_array[len(word)].append(word[::-1])

    for i in range(10001):
        word_array[i].sort()
        reversed_word_array[i].sort()
        
    for query in queries:
        if query[0] != '?':
            answer.append(count_by_range(word_array[len(query)],query.replace('?','a'),query.replace('?','z')))
        else:
            reversed_query=query[::-1]
            answer.append(count_by_range(reversed_word_array[len(query)],reversed_query.replace('?','a'),reversed_query.replace('?','z')))
    return answer