Programmers : 순위 검색

풀이 요약

구현 문제 (단 효율성 테스트를 통과하기 위해서는 완탐, 순열, 정렬 등의 최적화 알고리즘이 적용되어야 함)

풀이 상세

1. 먼저 사전에 info 값을 - 와 섞어서, 해당 info 값이 반영될 수 있는 모든 쿼리를 미리 만들어둔다.

2. 예를 들어, java backend junior pizza 라고 한다면 이와 알맞는 쿼리들은 다음과 같다.

   • - - - -
   • java - - -
   • java backend - -
   • java - junior -
   • …

3. 총 나타날 수 모든 경우의 수는 단어가 총 4개, 각각 단어 그리고 - 가 들어갈 수 있으므로 총 경우의 수는 16가지이다. 경우의 수가 적기 때문에 비트마스킹을 활용할 수 있다.

4. 비트마스킹을 통해 나타난 모든 키 값을 Map 의 키 값으로 반영시킨다. map 의 value 는 코테 점수를 반영시키도록 vector 를 만들어줬다.

5. 빠른 탐색을 위해, 키의 모든 vector 를 오름차순 정렬한다.

6. 만약 임의의 쿼리가 반영되는 키 값이 존재하는 경우, 쿼리의 코테 점수와 vector 의 점수를 비교 하여, lower_bound 값을 찾는다. 반환 값은 현재 점수 이상의 값을 찾기 때문에, 해당하는 최저 값의 인덱스를 찾아, 마지막 인덱스를 빼주면 해당 쿼리에 일치하는 총 결과 갯수가 나오게 된다.

정답

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

vector<string> split(string str, string deli) {
    vector<string> result;
    long long pos = 0;
    string token;
    while ((pos = str.find(deli)) != string::npos) {
        token = str.substr(0, pos);
        result.push_back(token);
        str.erase(0, pos + deli.length());
    }
    pos = 0;
    token = "";
    while ((pos = str.find(" ")) != string::npos) {
        token = str.substr(0, pos);
        result.push_back(token);
        str.erase(0, pos + 1);
    }
    result.push_back(str);
    return result;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    map<string, vector<int>> db;
    for (auto i: info) {
        vector<string> curr_info = split(i, " ");
        for (int j = 0; j < 16; j++) {
            string tmp = "";
            for (int k = 0; k < 4; k++)
                tmp += (j & (1 << k)) ? curr_info[k] : "-";
            db[tmp].push_back(stoi(curr_info[4]));
        }
    }

    for (auto &v: db) sort(v.second.begin(), v.second.end());

    for (auto q: query) {
        vector<string> curr_query = split(q, " and ");
        string key = curr_query[0] + curr_query[1] + curr_query[2] + curr_query[3];
        vector<int> scores = db[key];
        answer.push_back(scores.end() - lower_bound(scores.begin(), scores.end(), stoi(curr_query[4])));
    }

    return answer;
}