[2020 카카오 신입 공채 1차] 가사 검색

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

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

---

 풀이1

 문자열을 다루는 문제를 유독 많이 출제하는 카카오이지만 문자열 이진탐색은 덕분에 처음 접해본 듯 합니다. 처음에 접근했던 코드는 다음과 같습니다.

 

def solution(words, queries):
    import re

    array = []

    for q in queries:
        length = len(q)
        pos = 'pre' if q[-1] == '?' else 'post'
        keyword = re.sub('\?', '', q)
        cnt = 0

        tmp_words = sorted([w for w in words if len(w) == length])
        for w in tmp_words:
            if pos == 'pre':
                if w[:len(keyword)] == keyword:
                    cnt += 1
            else:
                if w[-len(keyword):] == keyword:
                    cnt += 1
        array.append(cnt)
    print(array)

 

 핵심 아이디어는 제약 조건이 2개라는 점입니다. 첫번째는 길이입니다. 쿼리에서 물음표까지 포함한 문자열의 길이가 words의 원소의 길이와 맞지 않는다면 매칭되지 않습니다. 두번째는 패턴입니다. 물음표를 제외한 나머지 문자열이 같은 패턴을 보여야 합니다. 단, 물음표는 앞 혹은 뒤에서부터 연속으로만 출현하기 때문에, 두 경우를 나누어서 구현해주었습니다.

 

 위의 코드로도 정확성 평가는 100점을 맞을 수 있지만, 효율성은 매우 좋지 않습니다. words의 원소의 개수는 100,000개 이하이고 queries의 원소의 개수도 역시 100,000개 이하입니다. 따라서 words의 원소의 개수를 N, queries의 원소의 개수를 M이라고 할 때 시간복잡도 O(N * M) 의 코드를 작성할 경우 10,000,000,000번(100억 번)의 연산이 필요하여 1초를 초과하게 됩니다.

 

 따라서 다음과 같이 코드를 수정했을 때 효율성 점수 만점을 받을 수 있었습니다.

 

---

풀이2

def solution(words, queries):
    from bisect import bisect_left, bisect_right

    def count_by_range(a, left_value, right_value):
        left = bisect_left(a, left_value)
        right = bisect_right(a, right_value)
        return right - left

    arrays = []
    reverse_arrays = []
    for _ in range(10000):
        arrays.append([])
        reverse_arrays.append([])

    for w in words:
        arrays[len(w)].append(w)
        reverse_arrays[len(w)].append(w[::-1])

    for i in range(10000):
        if len(arrays[i]) != 0:
            arrays[i].sort()
            reverse_arrays[i].sort()

    answer = []
    for q in queries:
        if q[-1] == '?':
            tmp_words = arrays[len(q)]
        else:
            tmp_words = reverse_arrays[len(q)]
            q = q[::-1]

        cnt = count_by_range(tmp_words, q.replace('?', 'a'), q.replace('?', 'z'))
        answer.append(cnt)


    return answer

 

 순차탐색에 비해 이진탐색 알고리즘은 시간복잡도가 O(logN)입니다. 따라서 words 혹은 queries 중 하나만 이진탐색을 수행하도록 바꾸더라도 최악의 경우 대략 10,000,000(백만 번)의 연산이 소요되며, 충분히 효율적인 코드라고 할 수 있습니다.

 위 코드에서는 더욱 효율적인 탐색 과정을 위해서 길이 제한 조건을 미리 리스트에 초기화시켜주었습니다. 즉, 길이별로 나누어 문자열을 받아오도록 하였습니다. 각 키워드는 10,000 이하 길이를 가진다고 했으므로 리스트 내에 10,000개의 리스트를 넣어 초기화시켜줍니다. 그 후 길이에 해당하는 인덱스에 문자열을 append 시킵니다.

 중요한 것은 앞쪽 문자열에 대한 쿼리, 뒤쪽 문자열에 대한 쿼리, 두 종류가 있으므로 이를 대비하기 위해서 뒤집힌 문자열이 들어간 reverse_arrays도 만들어주었습니다. 이후 이어질 이진탐색에 대비하여 미리 리스트를 문자열에 대해 정렬시킵니다.

arrays = []
reverse_arrays = []
for _ in range(10000):
    arrays.append([])
    reverse_arrays.append([])

for w in words:
    arrays[len(w)].append(w)
    reverse_arrays[len(w)].append(w[::-1])
    
for i in range(10000):
    if len(arrays[i]) != 0:
        arrays[i].sort()
        reverse_arrays[i].sort()

 핵심은 다음 부분입니다. 물음표가 뒤에 존재하는가, 앞에 존재하는가에 따라 조건을 분기해서 처리합니다. 탐색 시 미리 구현해놓은 count_by_range 함수를 이용합니다.

from bisect import bisect_left, bisect_right

def count_by_range(a, left_value, right_value):
    left = bisect_left(a, left_value)
    right = bisect_right(a, right_value)
    return right - left

 bisect_left는 왼쪽에서부터 해당 원소가 리스트의 어디에 들어가야하는지 위치를 반환합니다. 반대로 bisect_right는 오른쪽에서부터 위치를 반환합니다. 따라서 쿼리가 'fro??'일 경우 'froaa'부터 'frozz'까지의 위치를 찾아 두 위치의 차이를 구하고, 이를 반환한다면 'fro??'라는 쿼리에 매칭되는 단어의 수를 구할 수 있게 됩니다.

 단어의 수는 쿼리마다 구해져서 answer에 append됩니다.

cnt = count_by_range(tmp_words, q.replace('?', 'a'), q.replace('?', 'z'))
answer.append(cnt)

 

정리

 숫자 뿐만 아니라 문자도 정렬시킬 수 있다는 것, 그리고 이진탐색을 이용한 시간 복잡도 개선 등 배경지식이 혼합되어야만 만점을 받을 수 있는 문제였습니다. 이전부터 느끼는거지만 카카오의 문제는 정말 하나하나 쉽지 않은 것 같습니다.