프로그래머스 순위검색 C++

문제

https://programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

 

코드

#include <bits/stdc++.h>

using namespace std;

vector<vector<string>> v;
unordered_map<string, vector<int>> m; //query, score

vector<string> split(string input, char delimiter) {
    vector<string> answer;
    stringstream ss(input);
    string temp;
 
    while (getline(ss, temp, delimiter)) {
        if(temp == "and" || temp == "-") 
            continue;
        answer.push_back(temp);
    }
 
    return answer;
}

void makeCombi(vector<string> v) {
    for(int i = 1; i <= (1 << 4); i++) {
        string query;
        for(int j = 0; j < 4; j++) {
            if(i & (1 << j)) {
                query += v[j];
            }
        }
        
        if(query.empty())
            query = "onlyScore";

        m[query].push_back(stoi(v[4]));
    }
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    for(int i = 0; i < info.size(); i++) {
        vector<string> temp = split(info[i], ' ');
        makeCombi(temp);
    }
    
    for(auto& s : m) {
         sort(s.second.begin(), s.second.end());
    }

    for(const auto& q : query) {
        vector<string> temp = split(q, ' ');
        string tempQuery;
        for(int i = 0; i < temp.size() - 1; i++){
            tempQuery += temp[i];
        }
        
        if(tempQuery.empty())
            tempQuery = "onlyScore";

        vector<int> scores = m[tempQuery];
        if(scores.size()) {
            auto iter = lower_bound(scores.begin(), scores.end(), stoi(temp[temp.size()-1]));
            answer.push_back(scores.size() - (iter - scores.begin()));
        } else {
            answer.push_back(0);
        }
    }
    
    return answer;
}

→ 분명 스트링 문제이긴하나......... 풀이법을 보니 굉장히 여러 풀이법이 존재함.

지원자들의 정보를 조합하여 쿼리를 만들고, 쿼리와 매칭되는 점수를 이분탐색하는 문제.

• 점수를 이분탐색 하는것까지는 생각했으나, 지원자들 정보를 바탕으로 조합 쿼리를 만든 후에 이분탐색 하는걸 생각하지 못했음.
• 문제를 자세히 뜯어보면, 이 문제에서 요구하는건 ~ 조건을 가진 몇점 이상 지원자를 구하는 것이기 때문에
  • ~ 조건을 가진 지원자 = > 조합으로 구해놓고
  • 몇점 이상 지원자  = > 이분탐색으로 구하면된다.
• 조합은 비트마스킹을 이용했고,  unordered_map<쿼리, vector<쿼리에 해당되는 점수>를 담았음.
• 맵에서 키 = 쿼리, 값 = vector<점수> 로 담은 다음에 vector<점수> 를 이분탐색했음
• 정말 좋은 문제에 좋은 풀이법같다.