프로그래머스 - 순위검색

3*2*2*2 케이스에 대해 벡터를 만들고 값을 집어 넣는다

그 후 정렬한 뒤 각각 upper bound를 구하며 쿼리문의 결과를 구한다.

 

돌아돌아 구현한 느낌이 드는데 

더 간단한 풀이가 있는지 찾아봐야겠다.

 

#include <string>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <algorithm>
 
using namespace std;
vector<int> v[3][2][2][2];
vector<int> num;
unordered_map<string, int> mp;
int cnt[4]={3,2,2,2};
 
int upper_bound(vector<int> &a, int target){
    int lo = 0;
    int hi = a.size();
    while(lo<hi) {
        int mid = (lo+hi)/2;
        if(a[mid]<target){
            lo = mid+1;
        }
        else {
            hi = mid;
        }
    }
    return hi;
}
 
int dfs(vector<string> &b, int dep, int score){
    if(dep==4){
        vector<int> &vvv = v[num[0]][num[1]][num[2]][num[3]];
        if(vvv.size()==0) return 0;
        return vvv.size()-upper_bound(vvv, score);
    }
    
    int sum=0;
    
    if(b[dep]=="-"){
        for(int i=0;i<cnt[dep];i++){
            num.push_back(i);
            sum+=dfs(b, dep+1, score);
            num.pop_back();
        }
        
    }
    else{
        num.push_back(mp[b[dep]]);
        sum += dfs(b, dep+1, score);
        num.pop_back();
    }
    return sum;
}
 
 
vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    mp["cpp"]=0; mp["java"]=1; mp["python"]=2;
    mp["backend"]=0; mp["frontend"]=1;
    mp["junior"]=0; mp["senior"]=1;
    mp["chicken"]=0; mp["pizza"]=1;
    
    for(int i=0;i<info.size();i++){
        string s = info[i];
        
        vector<string> ss;
        int cnt=0;
        int idx=-1;
        for(int j=0;j<s.size();j++){
            if(s[j]==' '){
                ss.push_back(s.substr(idx+1, j-idx-1));
                idx=j;
                cnt++;
            }
            if(cnt==4){
                int tmp = stoi(s.substr(idx+1, s.size()-idx-1));
                v[mp[ss[0]]][mp[ss[1]]][mp[ss[2]]][mp[ss[3]]].push_back(tmp);
                break;
            }
        }
    }
    
    for(int i=0;i<3;i++){
        for(int j=0;j<2;j++){
            for(int k=0;k<2;k++){
                for(int l=0;l<2;l++){
                    sort(v[i][j][k][l].begin(), v[i][j][k][l].end());
                }
            }
        }
    }
    
    
    for(int i=0;i<query.size();i++){
        string s = query[i];
        
        vector<string> ss;
        int cnt=0;
        int idx=-1;
        int score;
        for(int j=0;j<s.size();j++){
            if(s[j]==' '){
                ss.push_back(s.substr(idx+1, j-idx-1));
                cnt++;
                if(cnt!=4) j+=4;
                idx=j;
            }
            if(cnt==4){
                score = stoi(s.substr(idx+1, s.size()-idx-1));
                break;
            }
        }
        answer.push_back(dfs(ss, 0, score));
    }
    
    return answer;
}