프로그래머스 - 순위 검색

프로그래머스 - 순위 검색

어렵지는 않은 문젠데, 효율성 테스트 때문에 까다롭다.

• cpp java python : 0 1 2 3
• backend frontend : 0 1 3
• junior senior : 0 1 2
• chicken pizza : 0 1 2

위와 같이 Index를 두고, 알맞은 Bucket에 유저의 점수를 입력해둔다.
예를 들어, java, backend, junior, chicken 이라면 54번째 Bucket이 본인의 Bucket이 될 것이다.
그러나 "-"를 고려해야 하기 때문에 java, "-", junior, chicken에 해당하는 Bucket에도 점수를 넣어두고, java, "-", "-", chicken 등에 해당하는 Bucket에도 점수를 넣어둬야 한다.
Bucket을 결정하는 Index는 총 4가지이므로, 2의 4승개인 16개의 Bucket에 점수를 넣어둬야 하는 것이다.
총 108개 (4 x 3 x 3 x 3) 의 버켓이 존재할 수 있고, 1개의 유저는 16개의 알맞은 버켓에 자신의 점수를 넣어놓도록 하면 된다.

그 후 Query를 파싱해서 해당 Bucket에서 점수를 비교해서 같거나 높은 것만 세주면 된다. (만약 점수도 상관 없다면 그냥 해당 버켓의 크기를 정답으로 하면 된다)

코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;
/*
- cpp java python : 0 1 2 3
- backend frontend : 0 1 3
- junior senior : 0 1 2
- chicken pizza : 0 1 2
*/

const inline void get_idx(const vector<string> &str, int idx[4])
{
    for(int i=0;i<4;i++) idx[i] = 0;
    
    if(!str[0].compare("cpp")) 
        idx[0] += 27;
    else if(!str[0].compare("java"))
        idx[0] += 54;
    else if(!str[0].compare("python"))
        idx[0] += 81;
    if(!str[1].compare("backend"))
        idx[1] += 9;
    else if(!str[1].compare("frontend"))
        idx[1] += 18;
    if(!str[2].compare("junior"))
        idx[2] += 3;
    else if(!str[2].compare("senior"))
        idx[2] += 6;
    if(!str[3].compare("chicken"))
        idx[3] += 1;
    else if(!str[3].compare("pizza"))
        idx[3] += 2;
}

const inline void get_bucket_list(int idx[4], int bucket_list[16])
{
    bucket_list[0] = idx[0] + idx[1] + idx[2] + idx[3];
    bucket_list[1] = idx[0] + idx[1] + idx[2];
    bucket_list[2] = idx[0] + idx[1] + idx[3];
    bucket_list[3] = idx[0] + idx[1];
    bucket_list[4] = idx[0] + idx[2] + idx[3];
    bucket_list[5] = idx[0] + idx[2];
    bucket_list[6] = idx[0] + idx[3];
    bucket_list[7] = idx[0];
    bucket_list[8] = idx[1] + idx[2] + idx[3];
    bucket_list[9] = idx[1] + idx[2];
    bucket_list[10] = idx[1] + idx[3];
    bucket_list[11] = idx[1];
    bucket_list[12] = idx[2] + idx[3];
    bucket_list[13] = idx[2];
    bucket_list[14] = idx[3];
    bucket_list[15] = 0;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    vector<vector<int>> user_list(108); 
    for(int i=0;i<info.size();i++) {
        string tmp = "";
        vector<string> info_str;
        for(int j=0;j<info[i].size();j++) {
            if(isspace(info[i][j])) {
                info_str.push_back(tmp);
                tmp = "";
                continue;
            } 
            tmp += info[i][j];  
        }
        info_str.push_back(tmp);
        
        int idx[4]; get_idx(info_str, idx);
        int bucket_list[16]; get_bucket_list(idx, bucket_list);
        for(int j=0;j<16;j++) 
            user_list[bucket_list[j]].push_back(stoi(info_str[4]));
    }
    
    for(int i=0;i<query.size();i++) {
        string tmp = "";
        vector<string> query_str;
        for(int j=0;j<query[i].size();j++) {
            if(isspace(query[i][j])) {
                if(tmp.compare("and") != 0) 
                    query_str.push_back(tmp);
                tmp = "";
                continue;
            }
            tmp += query[i][j];  
        }
        query_str.push_back(tmp);

        int idx[4]; get_idx(query_str, idx);
        int bucket = idx[0] + idx[1] + idx[2] + idx[3];
        if(query_str[4].compare("-") == 0) 
            answer.push_back(user_list[bucket].size());
        else {
            int cnt = 0;
            int grade = stoi(query_str[4]);
            for(int j=0;j<user_list[bucket].size();j++) 
                if(user_list[bucket][j] >= grade)
                    cnt++;
            answer.push_back(cnt);
        }
    }

    return answer;
}