[알고리즘] - 가사 검색 (2020 카카오 공채)

• 이번 문제는 2020년 카카오 신입 공채 문제 ‘가사 검색’ 입니다. 문제 명세 및 입출력 예시는 링크를 참고해주세요!

접근 방식

• queries 안의 각 쿼리 단어들과 words 안의 단어들의 비교 과정에서의 편의를 위해, words 배열을 해당 원소들의 길이에 따라서 이차원 리스트로 만듭니다.
  • 예를 들어 “frodo”는 글자수가 5이기 때문에 리스트의 [5] 위치에 저장합니다.
  • 이런식으로 글자수에 따라서 각각의 위치에 해당하는 단어들을 리스트로 저장합니다.
• 위와 같이 비교의 편의를 위해 단어들을 글자수에 맞게 나눈다고 해도, worst case의 경우 최대 10만개의 쿼리들이 각 쿼리마다 10만개의 단어들과 비교 연산을 수행하게 됩니다.
  • 이 경우 최대 10,000,000,000 (100억) 번의 연산이 수행되기 때문에 시간복잡도가 매우 높아지게 됩니다.
  • 따라서 이를 줄이기 위해 이진 탐색을 수행합니다.
• python bisect 라이브러리의 bisect_right과 bisect_left를 활용하여 그 사이에 존재하는 단어들의 개수를 구합니다.
  • 예를 들어 “fro??”에 일치하는 단어들을 찾기 위해, “froaa”와 “frozz” 사이의 단어들을 찾게 됩니다.
  • 이는 제약 조건 상 영어 소문자만 가능하다는 점을 활용하여, fro??에서 ??에 어떤 영어 소문자가 들어가도 해당 단어들을 카운팅 할 수 있도록 합니다.

구현

• 현재의 쿼리인 query와, 동일한 글자수를 가진 단어 리스트(비어 있지 않은 경우만)를 입력으로 받아 해당 리스트 안에서 패턴에 일치하는 문자를 찾는 search_query함수는 아래와 같이 구현했습니다.

  def search_query(query, words):
    
      left_target = query.replace("?", "a")
      right_target = query.replace("?", "z")
    
      result = bisect_right(words, right_target) - bisect_left(words, left_target)
    
      return result
  

  • bisect_right 함수는 인자로 받은 원소보다 작거나 같은 원소들이 모두 왼쪽에 갈 수 있도록 해당 원소를 배치합니다. 즉, 예를 들어 bisect_right(words, “frozz”)의 경우 “frozz”보다 사전순으로 작거나 같은 원소들 바로 다음 위치의 인덱스를 반환합니다.
  • bisect_left 함수는 인자로 받은 원소보다 크거나 같은 원소들이 모두 오른쪽에 갈 수 있도록 해당 원소를 배치합니다. 즉, bisect_left(words, “froaa”)의 경우 “froaa”보다 사전순으로 크거나 같은 원소들의 바로 직전 위치의 인덱스를 반홥합니다.

• 그러나 이 함수는 기본적으로 “?” 문자가 뒤쪽에 위치하는 경우에만 올바른 정답을 반환합니다. 즉, “???fro”와 같은 문자에는 정상적으로 작동하지 않습니다.

아이디어

• 위의 문제를 해결하기 위해, 만약 “?” 문자가 앞쪽에 위치하는 “???fro”와 같은 문자열의 경우, 뒤집어서 접근하는 방식을 활용했습니다. 즉, “???fro”의 경우 “orf???”으로 쿼리를 변경합니다.
• 또한 동시에 단어들도 모두 거꾸로 담아 놓은 리스트를 미리 만들어서, 뒤집힌 쿼리와 뒤집힌 단어들끼리 위의 함수를 통해 비교를 수행하도록 했습니다.
• 이에 따라 단어들을 거꾸로 뒤집어 놓을 리스트를 하나 선언하고, 기존 리스트와 동일한 작업을 거칠 수 있도록 합니다.

소스 코드

from bisect import bisect_left, bisect_right

def search_query(query, words):

    left_target = query.replace("?", "a")
    right_target = query.replace("?", "z")

    result = bisect_right(words, right_target) - bisect_left(words, left_target)

    return result

def solution(words, queries):
    answer = []

    # words를 각 단어들의 길이에 따라서 나눠서 저장
    words_by_len = [None] * 10001 # 최대 길이 10000
    reverse_words = [None] * 10001

    for target in words:
        size = len(target)

        if not words_by_len[size]:
            # None일 경우 리스트 생성
            words_by_len[size] = []
            reverse_words[size] = []

        words_by_len[size].append(target)
        reverse_words[size].append(target[::-1]) # slice를 활용하여 간편하게 뒤집기

    # 이진 탐색을 위해, 각 words_by_len의 원소들, 즉 그 안의 단어 리스트들을 정렬
    for lst in words_by_len:
        if not lst:
            continue
        lst.sort()

    for rev in reverse_words:
        if not rev:
            continue
        rev.sort()

    # 각 쿼리마다 해당 쿼리 사이즈에 맞는 단어들의 리스트를 이진탐색으로 순회하며 키워드가 일치하는지 확인
    for query in queries:
        query_size = len(query)
        target_words = words_by_len[query_size]

        # target_words에 탐색을 위한 단어가 없다면, 해당 쿼리 자리에는 0을 추가
        if not target_words:
            answer.append(0)
            continue

        # query에서 ?가 앞부분에 나온다면 뒤집는 버전으로 함수 실행
        if query.find("?") == 0:
            match_num = search_query(query[::-1], reverse_words[query_size])
        else:
            match_num = search_query(query, target_words)

        answer.append(match_num)

    return answer


# 입출력 예시
words = ["frodo", "front", "frost", "frozen", "frame", "kakao"]
queries = ["fro??", "????o", "fr???", "fro???", "pro?"]

print(solution(words, queries))

• words_by_len 이라는 리스트를 새로 선언하여, 단어들을 길이에 따라서 분리하여 이차원 리스트로 선언했습니다.

• reverse_words 라는 리스트를 선언하여, 단어들을 뒤집은 뒤 words_by_len과 동일하게 길이에 따라 이차원 리스트로 저장했습니다.

• 만약 query가 “?”로 시작하는 단어라면 query를 뒤집은 뒤, reverse_words와 함께 search_query 함수에 넘겼습니다.

• 문자열을 뒤집는 과정에서는 가장 간단한 방식으로 [::-1] 과 같이 슬라이싱을 활용했습니다.

• 이진 탐색을 위해서는 search_query 함수로 들어가는 각 길이별 word 리스트들이 정렬되어 있어야 합니다. 이를 search_query 함수 내부적으로 수행할 수도 있지만, 이는 최악의 경우(동일한 길이의 단어 10만개가 존재하는 경우)에는 10만번에 걸쳐서 sort를 하게 되기 때문에 O(NlogN)의 복잡도를 갖는 파이썬 내장 정렬 함수라고 할지라도 시간복잡도가 매우 높아집니다. 이진탐색을 하는 효과가 없어지는 것입니다.

• 따라서 search_query 함수 내부적으로 수행하지 않고, 리스트를 초기화한 뒤 일괄적으로 리스트를 순회하며 리스트 안의 리스트들을 정렬해주는 과정을 거칩니다. 이 과정은 최대 1만개의 리스트에 분산되어 있는 도합 최대 10만개의 원소를 한 번씩만 거쳐가며 정렬하면 되기 때문에 시간복잡도에 큰 무리를 주지 않습니다.

Lesson

이 문제는 직접 풀어보니 이진탐색 카테고리에 속한다는 것을 알면서도 어떤 식으로 이진 탐색을 해야 하는지 감이 잘 오지 않았던 것 같습니다. 또한 이진 탐색을 하는 과정에서도 문자열을 다루는 테크닉과, 문자열을 뒤집어서 탐색한다는 아이디어가 필요했기 때문에 굉장히 난이도가 높게 느껴졌던 것 같습니다. 처음 문제를 접했을 때는 오래 고민했음에도 제대로 풀지 못했었는데, 두 번째에 보니 문제를 어떻게 접근해야 하는지가 조금은 보이는 것 같습니다. 역시 반복하면서 풀어봐야 될 것 같습니다. 추가로 한 번 문자열 관련 함수나 처리 방식을 정리해볼 필요가 있음을 느꼈습니다.

Reference

이것이 취업을 위한 코딩 테스트다 with 파이썬