[이진 탐색 알고리즘] 가사 검색 ★★★

기출 : 2020 카카오 신입 공채 1차

 

이 문제를 풀면서 정말 가장 많이 배우는 것 같다

 

지금까지 문자열을 다루는 어려운 문제들은 풀어본 적이 없었다

 

이 문제는 거의 외우다시피 해야 할 것 같다

 

일단 문제 풀이의 아이디어는 다음과 같다

 

1. 주어진 단어들을 길이별로 나눈 뒤 정렬하여 저장한다

2. 주어진 단어들을 리버스하여 1의 과정을 반복한다

3. 각 쿼리들에 대해 접두사/접미사 여부, 쿼리의 길이에 따라 카운트한다

 

이 문제를 풀면서 알고리즘 팀 노트의 필요성을 느꼈다

 

countByRange 함수, replaceAll 함수 등은 다른 문제에서도 자주 쓸 것 같아서 팀 노트를 작성했다

#include<bits/stdc++.h>
using namespace std;

int countByRange(vector<string> &v, string from, string to) {
    vector<string>::iterator lowerbound = lower_bound(v.begin(), v.end(), from);
    vector<string>::iterator upperbound = upper_bound(v.begin(), v.end(), to);
    return upperbound - lowerbound;
}

string replaceAll(string word, string from, string to) {
    string res = word;
    int pos = 0;
    while ((pos = res.find(from,pos))!= string::npos) {
        res.replace(pos, from.size(), to);
        pos += to.size();
    }
    return res;
}

vector<string> wordz[10001];
vector<string> revwordz[10001];

vector<int> solution(vector<string> words, vector<string> queries) {
    vector<int> answer;

    for (int i = 0;i < words.size();i++) {
        string word = words[i];
        wordz[word.size()].push_back(word);
        reverse(word.begin(), word.end());
        revwordz[word.size()].push_back(word);
    }

    for (int i = 0;i < 10001;i++) {
        sort(wordz[i].begin(), wordz[i].end());
        sort(revwordz[i].begin(), revwordz[i].end());
    }

    for (int i = 0;i < queries.size();i++) {
        string q = queries[i];
        int ans = 0;
        if (q[0] != '?') {
            ans = countByRange(wordz[q.size()], replaceAll(q, "?", "a"), replaceAll(q, "?", "z"));
        }
        else {
            reverse(q.begin(), q.end());
            ans = countByRange(revwordz[q.size()], replaceAll(q, "?", "a"), replaceAll(q, "?", "z"));
        }
        answer.push_back(ans);
    }
    return answer;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    vector<string> v,v2;
    v.push_back("frodo");
    v.push_back("front");
    v.push_back("frost");
    v.push_back("frozen");
    v.push_back("frame");
    v.push_back("kakao");

    v2.push_back("fro??");
    v2.push_back("????o");
    v2.push_back("fr???");
    v2.push_back("fro???");
    v2.push_back("pro?");

    vector<int> answer = solution(v,v2);
    for (int i = 0;i < answer.size();i++) cout << answer[i] << endl;

    return 0;
}