[프로그래머스] 순위 검색 (C++)

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

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

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

map<string, vector<int> > m;

void makeCombi(vector<vector<string> > &v, int score){
    for (int i=0; i<2; i++){
        for (int j=0; j<2; j++){
            for (int k=0; k<2; k++){
                for (int l=0; l<2; l++){
                    string temp=(v[0][i]+v[1][j]+v[2][k]+v[3][l]);
                    m[temp].push_back(score);
                }
            }
        }
    }
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    string s;
    int score, target;
    for (int i=0; i<info.size(); i++){
        stringstream ss;
        vector<vector<string> > v(4, vector<string>(1, "-"));
        ss.str(info[i]);
        for (int j=0; j<4; j++){
            ss>>s;
            v[j].push_back(s);
        }
        ss>>score;
        makeCombi(v, score);
    }
    for (auto it=m.begin(); it!=m.end(); it++){
        sort(it->second.begin(), it->second.end());
    }
    for (int i=0; i<query.size(); i++){
        stringstream ss;
        ss.str(query[i]);
        string q;
        for (int j=0; j<7; j++){
            ss>>s;
            if (s!="and"){
                q+=s;
            }
        }
        ss>>target;
        int cnt=lower_bound(m[q].begin(), m[q].end(), target)-m[q].begin();
        answer.push_back(m[q].size()-cnt);
    }
    return answer;
}

 

map을 이용해서 풀었다.

그리고 점수를 탐색할 때 미리 정렬해줘서 이분탐색하여 효율성을 높이는게 중요하다.

 

해당 info에서 나올 수 있는 모든 경우의 수를 map의 key에 넣어주고, value는 점수를 넣어준다.

예를 들어, "java backend junior pizza 100" 이라면, 2^4=16가지의 경우를 map의 키로 삼고, value를 100으로 하는 것이다.

쿼리문을 볼때는 해당 문자열들을 파싱하여, 맵의 해당하는 문자열에 해당하는 key의 value를 얻는다.

점수 배열인 value는 후에 다 정렬을 해줘서 이분탐색할 준비를 한다.

 

이분 탐색시에는 lower_bound를 써서, 해당 점수와 같거나 큰 인덱스를 찾아 해당 조건 수를 만족하는 총 인원수를 얻는다.