가사 검색 (lv4)

문제 설명

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

친구들로부터 천재 프로그래머로 불리는 "프로도"는 음악을 하는 친구로부터 자신이 좋아하는 노래 가사에 사용된 단어들 중에 특정 키워드가 몇 개 포함되어 있는지 궁금하니 프로그램으로 개발해 달라는 제안을 받았습니다.
그 제안 사항 중, 키워드는 와일드카드 문자중 하나인 '?'가 포함된 패턴 형태의 문자열을 뜻합니다. 와일드카드 문자인 '?'는 글자 하나를 의미하며, 어떤 문자에도 매치된다고 가정합니다. 예를 들어 "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??"('?'가 양쪽에 있음)는 불가능한 키워드입니다.

---

 문제에서의 요구사항을 그대로 따라가며 구현해봤다. 쿼리할 문자의 길이를 기준으로 이분탐색을 진행한 뒤, 원하는 길이로 구성된 문자열이 들어있는 리스트를 순회하며 와일드카드 문자인 '?' 를 제외한 쿼리 문자열이 제 위치에 있는지 확인하는 방식이다. 이 풀이는 테스트 케이스 자체는 통과할 수 있으나, 효율성 테스트에서 3 / 5 의 점수를 받아 실패한다. 매 쿼리마다 이분탐색으로 원하는 길이를 찾아 준다는 점, 와일드 카드가 앞 뒤 양쪽에 붙을 수 있기 때문에 쿼리 문자열 매칭은 이분 탐색이 아닌 O(n) 완전 탐색으로 진행한다는 점, 또 매 쿼리마다 와일드카드가 아닌 문자열을 찾아낸다는 점이 주 원인으로 생각된다.

코드

import re

glob_words = 0

def length_left(target,start,end):
    while start < end:
        mid = (start + end) // 2
        if target > len(glob_words[mid]):
            start = mid + 1
        else:
            end = mid
    return start

def length_right(target,start,end):
    while start < end:
        mid = (start + end) // 2
        if target >= len(glob_words[mid]):
            start = mid + 1
        else:
            end = mid
    return end - 1
    
def solution(words, queries):
    global glob_words
    glob_words = sorted(words, key = len)
    length = len(words)
    answer = []
    for query in queries:
        result = 0
        l = len(query)
        start,end = length_left(l,0,length),length_right(l,0,length)
        m = re.search('\w+',query)
        if m:
            span,word = m.span(),m.group()
            for elem in glob_words[start:end+1]:
                if elem[span[0]:span[1]] == word:
                    result += 1
        else:
            result += len(glob_words[start:end+1])
        answer.append(result)
    return answer

 해답지는 위에서 도출해낸 시간 복잡도 문제를 완화해주는 방식으로 접근한다. 구조는 거의 같으나 words의 문자열들을 미리 길이별로 묶어주며, 와일드카드가 쿼리 문자열 앞에 오거나 뒤에 올 수밖에 없다는 점을 주목하여 이분탐색으로도 쿼리를 수행할 수 있도록 하였다.

from bisect import bisect_left,bisect_right,insort_left

class Dict:
    def __init__(self) -> None:
        self.words = dict()
        self._words = dict()
    def add(self,value):
        length = len(value)
        if self.words.get(length):
            insort_left(self.words[length], value)
            insort_left(self._words[length], value[::-1])
        else:
            self.words[length] = [value]
            self._words[length] = [value[::-1]]
    def get(self,key,*,reversed=False):
        if not reversed:
            return self.words[key] if self.words.get(key) else None
        else:
            return self._words[key] if self._words.get(key) else None

def count_by_range(a, left_value, right_value, *, reversed=False):
    if reversed:
        left_value,right_value = left_value[::-1],right_value[::-1]
    return bisect_right(a, right_value) - bisect_left(a, left_value) if a else 0

def solution(words, queries):
    answer = []
    dic = Dict()
    for word in words:
        dic.add(word)
    for query in queries:
        flag = query[0] == '?'
        li = dic.get(len(query),reversed=flag)
        answer.append(count_by_range(li,query.replace('?','a'),query.replace('?','z'),reversed=flag))
    return answer