알고리즘 :: 프로그래머스 :: 2020 카카오 :: 이진탐색 :: 가사 검색 (C++)

문제

문제 링크: https://programmers.co.kr/learn/courses/30/lessons/60060?language=cpp

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

문제접근

문제 풀이 전

• 효율성 테스트를 통과하기 위해 문제의 조건을 탐독한다.
  1. words의 길이 (가사 개수)와 queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하.
  2. 각 가사 단어와 쿼리 단어의 길이는 1 이상 10,000 이하.
  3. words에는 중복되는 가사(단어)가 없다.
  4. 모든 단어는 오직 알파벳 소문자로만 구성.
     쿼리문은 알파벳 소문자 + ? 와일드카드 문자로 이뤄져있음.
• 최악의 경우, $10만 \times 10만 \times 1만$번 문자 비교 연산을 수행해야하므로 bruteforce와 같은 $O(n)$ 풀이로는 문제를 해결할 수 없음을 깨닫는다.
• 그러므로, 이 문제는 $O(logN)$으로 풀어야 하는 이진 탐색 문제임을 알아차린다.

문제 풀이 관련

• 문제의 조건에 따르면 와일드카드 문자가 가지는 조건은 다음과 같다.
  1. 검색 키워드에는 와일드카드 문자가 적어도 하나 들어간다.
  2. 와일드카드 문자는 접두사 또는 접미사에 들어간다.

     • Q. 와일드카드 문자가 접미사에 있다면?
       A. 일반적인 방법대로 문자열을 앞에서부터 비교해야 한다.

     • Q. 와일드카드 문자가 접두사에 있다면?
       A. 문자를 뒤에서부터 비교해야 한다. → 비용이 너무 많이 든다.

       ∴ words내 모든 가사를 정방향과 역방향으로 나눠서 저장한다

• 외부 저장 공간은 가사의 길이에 따라 해시 테이블 형태로 저장한다.
  • e.g) beauty = 6글자 → hashTable[6].push_back("beauty")
• 해시 테이블에 대해 이진 탐색을 수행할 것이므로 sort()연산은 필수다.
• 검색 키워드를 순서대로 검사하며 와일드카드 문자가 접미사에 있다면 정방향 해시 테이블에 대해 이진 탐색을 수행하고, 접두사에 있다면 역방향 해시 테이블에 대해 이진 탐색을 수행한다.
• 이진 탐색은 lower_bound(), upper_bound() 두 함수를 이용하고,
  upper_bound() - lower_bound()가 검색 키워드 검색 결과(찾은 개수)가 된다.

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

// words 내 원소 길이 별 해시 테이블 (arr: 정방향, reverseArr: 역방향)
vector<string> arr[10001], reverseArr[10001];

// origin 문자열에서 `from` 문자를 `to`로 치환한다.
string userReplace(string origin, string from, string to) {
    int pos = origin.find(from, 0);	// from 문자가 발견되는 첫 번째 위치 반환.
    while (pos < origin.length()) {	// origin 문자열 끝까지 순회하면서 변경.
        origin.replace(pos, from.size(), to);
        pos += to.size();
    }
    return origin;
}

// `vec`에서 찾으려는 문자열의 개수를 반환한다.
int getCount(const vector<string>& vec, string left, string right) {
    auto rightIdx = upper_bound(begin(vec), end(vec), right);
    auto leftIdx = lower_bound(begin(vec), end(vec), left);
    // (e.g. fr??? -> fraaa ~ frzzz 영역 내에 있는 문자열 개수 반환.)
    return rightIdx - leftIdx;
}

vector<int> solution(vector<string> words, vector<string> queries) {
	// [과정 1]:: 모든 가사를 길이 별로 해시테이블에 저장한다.
    for (auto& itr : words) {
        arr[itr.length()].push_back(itr);	// 정방향 해시테이블에 저장.
        reverse(begin(itr), end(itr));
        reverseArr[itr.length()].push_back(itr);// 역방향 해시테이블에 저장.
    }
	// [과정 2]:: 해시테이블 내 모든 요소를 알파벳 순으로 정렬한다.
    for (auto& itr : arr) sort(begin(itr), end(itr));
    for (auto& itr : reverseArr) sort(begin(itr), end(itr));
	// [과정 3]:: 쿼리문의 '?'가 접두부에 있는지 접미부에 있는지 판단 후 계산한다.
	vector<int> answer;
    for (auto& itr : queries) {
        int res = 0;
        if (itr[0] == '?') {
            reverse(begin(itr), end(itr));
            res = getCount(reverseArr[itr.length()], userReplace(itr, "?", "a"), userReplace(itr, "?", "z"));
        } else 
            res = getCount(arr[itr.length()], userReplace(itr, "?", "a"), userReplace(itr, "?", "z"));
        answer.push_back(res);
    }
    return answer;
}

결과