[카카오] 가사검색

문제 이해하기

주어진 쿼리가 있고, 그 중에 몇 개의 월드가 매칭되는지 찾는 문제였다.

참고로 필자는 틀렸고, 어떤 접근 방법을 통해서 틀렸는지 설명하고 풀이법을 설명하겠다.

틀린 문제 해결 접근 과정

1. 경우의 수 검색하기

문제의 경우의 수를 보면 주어진 word의 길이는 100,000이고 word[x]의 길이는 최대 10,000이 된다.

따라서 word를 하나씩 분리하면 해결이 가능하지 않을까 싶었다. 왜냐하면 분리에 N*M의 경우의 수만 사용하면 됐기 때문이다

예시
f????
fr???
fro??
frod?
????o
???do
.....
?????

 

그 후 분리된 값들을 아래와 같은 방식으로 캐시에 저장하고 쿼리 배열 탐색을 cache에 찾아서 꺼내는 방식이었다.

cache['fr???] += 1

하지만 효율성4, 5에서 시간 초과가 발생했고, 그 이유는 N*M이 1억인줄 알았는데 10억이었다.

 

제대로 된 문제 해결 방법

 

1. 문자열 형식을 변경 후 이분탐색

"?" 문자는 어떤 문자든지 치환할 수 있다. 즉 ?문자 모두를 a와 z로 변경한다면 쿼리의 끝과 시작이 되게 된다.

예를들면 "fro???"의 가사를 찾는다고 가정한다면 froaaa ~ frozzz는 fro???로 검색될 수 있는 모든 범위를 포함하게 되는 것이다.

 

그렇다면 해당 구간의 범위를 빠르게 찾는 방법이 필요한데 이 때 이분탐색을 수행한다. froaaa, frozzz의 값들이 어디에 삽입되는지 찾고 그 구간을 빼주면 fro???로 검색하는 word의 개수가 된다.

def count(words, left_value, right_value):
    right_index = bisect_right(words, right_value)
    left_index = bisect_left(words, left_value)
    
    return right_index - left_index
    
for query in queries:
    if query[0] == '?':
        ans = count(reserve_cache[len(query)], query[::-1].replace('?', 'a'), query[::-1].replace('?', 'z'))
    else:    
        ans = count(cache[len(query)], query.replace('?', 'a'), query.replace('?', 'z'))
    answer.append(ans)

 

 

2. ?로 시작하는 문자열을 대비해서 word의 문자열도 역으로 정렬 

"?"문자가 앞에서 나온다면 단어를 뒤집어줘야 한다. 문자열의 정렬은 앞에서 부터 수행되기 때문이다.

 

예를들면 '???o'가 있으면 aaao ~ zzzo와 oaaa ~ ozzz는 다른 것이다. 후자의 경우는 o를 반듯이 포함하지만 전자의 경우에는 o를 반듯이 포함하지 않는다.

 

즉 word에 bbbb라는 문자가 있고 우리가 aaao ~ aaaz를 찾는다고 가정한다면 bbbb는 검색되면 안되는 문자인데 검색이 되게 된다.

for word in words:
    cache[len(word)].append(word)
    reserve_cache[len(word)].append(word[::-1])

for key in cache.keys():
    cache[key].sort()
    reserve_cache[key].sort()

 

코드

from bisect import bisect_left, bisect_right
from collections import defaultdict

def count(words, left_value, right_value):
    right_index = bisect_right(words, right_value)
    left_index = bisect_left(words, left_value)
    
    return right_index - left_index

def solution(words, queries):
    answer = []
    cache = defaultdict(list)
    reserve_cache = defaultdict(list)
    
    for word in words:
        cache[len(word)].append(word)
        reserve_cache[len(word)].append(word[::-1])
        
    for key in cache.keys():
        cache[key].sort()
        reserve_cache[key].sort()
        
    for query in queries:
        if query[0] == '?':
            ans = count(reserve_cache[len(query)], query[::-1].replace('?', 'a'), query[::-1].replace('?', 'z'))
        else:    
            ans = count(cache[len(query)], query.replace('?', 'a'), query.replace('?', 'z'))
        answer.append(ans)
        
    return answer

if __name__ == "__main__":
    words = ["frodo", "front", "frost", "frozen", "frame", "kakao"] #
    queries = ["fro??", "????o", "fr???", "fro???", "pro?"]
    print(solution(words, queries)) # [3, 2, 4, 1, 0]

 

배운점 정리하기

문자를 aaa와 zzz로 변경해서 주어진 배열중 어디에 삽입될 수 있을 지 판단하는 것 삽입될 위치도 O(n)이 아니라 이분탐색을 통해서 더 빠르게 접근하는 것

 

https://piaflu.tistory.com/82

[코딩테스트] 프로그래머스 - 가사 검색(2020 Kakao) in Python