[카카오코테] 가사 검색

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

친구들로부터 천재 프로그래머로 불리는 프로도는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어  "fro??"는 "frodo", "front", "frost" 등에 매치되지만 "frame", "frozen"에는 매치되지 않습니다.

가사에 사용된 모든 단어들이 담긴 배열 words와 찾고자 하는 키워드가 담긴 배열 queries가 주어질 때, 각 키워드 별로 매치된 단어가 몇 개인지 순서대로 배열에 담아 반환하도록 solution 함수를 완성해 주세요.

가사 단어 제한사항

• words의 길이(가사 단어의 개수)는 2 이상 100,000 이하입니다.
• 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 가사 단어 길이의 합은 2 이상 1,000,000 이하입니다.
• 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공됩니다.
• 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.

검색 키워드 제한사항

• queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하입니다.
• 각 검색 키워드의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없습니다.
• 전체 검색 키워드 길이의 합은 2 이상 1,000,000 이하입니다.
• 검색 키워드는 중복될 수도 있습니다.
• 각 검색 키워드는 오직 알파벳 소문자와 와일드카드 문자인 '?'로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정합니다.
• 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다.
  • 예를 들어 "??odo", "fro??", "?????"는 가능한 키워드입니다.
  • 반면에 "frodo"('?'가 없음), "fr?do"('?'가 중간에 있음), "?ro??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

입출력 예

 

words	queries	result
["frodo", "front", "frost", "frozen", "frame", "kakao"]	["fro??", "????o", "fr???", "fro???", "pro?"]	[3, 2, 4, 1, 0]

입출력 예에 대한 설명

• "fro??"는 "frodo", "front", "frost"에 매치되므로 3입니다.
• "????o"는 "frodo", "kakao"에 매치되므로 2입니다.
• "fr???"는 "frodo", "front", "frost", "frame"에 매치되므로 4입니다.
• "fro???"는 "frozen"에 매치되므로 1입니다.
• "pro?"는 매치되는 가사 단어가 없으므로 0 입니다.

 

 

 

 

 

초기접근

---

데이터가 많고 효율성 고려를 해야하는 문제였다.

그래서 어느부분에 이진탐색법을 도입해야 효율적일지 고민했다.

 

문제를 풀기위한 설계는 일단,

1. query와 같은 길이의 단어를 찾고

2. ? (와일드카드)를 고려해 비교한다.

1번은 이진탐색을 도입하면 logn 에 찾을 수 있고 2번은 해당하는 길이의 배열과 모두 비교하는 식으로 해도 될 것 같았다.

 

기존에 "특정 원소 개수 찾기" 에서 썼던 이진탐색기법을 이용해서 해당 query와 맞는 단어의 길이를 찾도록 했다.

2021/02/05 - [Algorithm/Binary Search] - [Zoho 인터뷰] 특정 원소 개수 찾기

[Zoho 인터뷰] 특정 원소 개수 찾기

 

그리고 그 범위만큼 query와 비교하도록 구현했다.

 

 

 

시간초과가 났다.

 

그래서 2번에도 효율성을 고려해야겠다 싶어서 이번에는 단어 하나마다 한글자씩 비교하는게 아닌

정규표현식으로 그냥 비교 해버리는걸로 구현을 했다.

 

코드

import re

def cal_left(words, length, start, end):
    if start > end:
        return None

    mid = (start + end) // 2
    if len(words[mid]) == length and (mid == 0 or len(words[mid-1]) < length):
        return mid
    elif length <= len(words[mid]):
        return cal_left(words, length, start, mid-1)
    else:
        return cal_left(words, length, mid+1, end)


def cal_right(words, length, start, end):
    if start > end:
        return None

    mid = (start + end) // 2
    if len(words[mid]) == length and (mid == len(words)-1 or len(words[mid+1]) > length):
        return mid
    elif length < len(words[mid]):
        return cal_right(words, length, start, mid-1)
    else:
        return cal_right(words, length, mid+1, end)




def count_value(query, length, words):
    n = len(words)
    left_index = cal_left(words, length, 0, n-1)
    if left_index is None:
        return 0

    right_index = cal_right(words, length, 0, n-1)
    count = 0

    query = query.replace("?", ".")
    p = re.compile(query)

    for i in range(left_index, right_index+1):
        if p.match(words[i]) is not None:
            count += 1
    return count



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

    words.sort(key=lambda x:len(x))

    for q in queries:
        length = len(q)
        answer.append(count_value(q, length, words))

    return answer

 

• cal_left(), cal_right() : query 글자 수와 같은 글자들의 인덱스를 찾는 함수
• count_value : 정규표현식으로 단어를 비교해서 개수를 세는 함수

 

실행결과

 

 

이번에도 시간초과가 났다.

 

내 코드에서 반복이 얼마나 진행되는지 다시 살펴보았다.

 

(query 수) x (같은 글자수의 인덱스 찾기 O(log n)) x (인덱스만큼 반복) = O(n^2 long n) 이었다.

n이 10만개이므로 n^2정도만 나와도 시간초과가 났을 것이다.

 

그래서 시간을 파격적으로 줄일 수 있는 방법을 찾아내야만 했다.

 

 

 

 

해결 아이디어

---

1. query와 같은 길이의 단어를 찾고

2. ? (와일드카드)를 고려해 비교한다.

 

이 설계는 그대로 가져갈 것이다.

하지만 1번을 O(log n)으로 단어마다 구하는 것이 아닌 딱 한번만 구하는 방법을 적용한다.

 

array = [[] for _ in range(10001)]

for word in words:
    array[len(word)].append(word)

미리 길이별로 배열에 집어 넣어 놓는 것이다. 그러면 같은 길이의 단어를 찾는것이 O(nlogn)이 아닌 그냥 상수시간에 끝난다.

 

코드

import re


def count_value(query, length, wordList):
    count = 0
    query = query.replace("?", ".")
    p = re.compile(query)

    for w in wordList:
        if p.match(w) is not None:
            count += 1
    return count


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

    array = [[] for _ in range(10001)]

    for word in words:
        array[len(word)].append(word)

    for i in range(10001):
        array[i].sort()

    for q in queries:
        length = len(q)
        answer.append(count_value(q, length, array[length]))

    return answer

실행결과

 

마찬가지로 또 시간초과가 난다.

 

문자열을 비교하는 부분에도 더 효율성을 고려해야 했다.

 

그래서 문자열 비교하는 부분에서 정규표현식을 빼고 이진탐색을 도입했다.

 

query가 fro?? 라면 같은 길이글자 배열 (array[len(query)])에서 froaa, frozz가 들어가는 위치를 bisect로 구하면 O(logn)에 알고리즘 전체가 돌아간다.

 

코드

from bisect import bisect_left, bisect_right


def count_value(a, left, right):
    left_index = bisect_left(a, left)
    right_index = bisect_right(a, right)
    return right_index - left_index


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

    array = [[] for _ in range(10001)]
    reverse_array = [[] for _ in range(10001)]


    for word in words:
        array[len(word)].append(word)
        reverse_array[len(word)].append(word[::-1])

    for i in range(10001):
        array[i].sort()
        reverse_array[i].sort()

    for q in queries:
        if q[0] != '?':
            res = count_value(array[len(q)], q.replace('?', 'a'), q.replace('?', 'z'))
        else:
            res = count_value(reverse_array[len(q)], q[::-1].replace('?', 'a'), q[::-1].replace('?', 'z'))
        answer.append(res)
    return answer

 

실행결과

확실히 빠른시간에 결과가 나오는 것을 볼 수 있다.

 

 

 

 

 

 

오래고민한 부분 & 깨달은 점

---

데이터가 많아서 이진탐색을 어느부분에 도입해야할 지 고민을 오래했다.

오래 고민해서 넣었지만 사실 상수시간에 끝낼 수 있는 부분이었다.

 

앞으로 문자열 개수를 구분할때 상수시간에 끝냈던 방법을 떠올려서 해결해야겠다.

 

그리고 이진탐색이 froaa, frozz 같은 방법으로도 적용될 수 있겠구나 생각이 든다.

효율성부분에 대한 채점이 있는 문제는 넓어진 시야로 이진탐색기법을 적용하도록 고민해야겠다.