[Programmers] 순위 검색

특정 조건을 모두 만족하는 경우를 고르는 문제이다.

문제해결전략
쿼리의 갯수가 10만, 인포의 갯수가 5만개 이므로 단순 비교작업의 경우 시간초과가 난다.

점수 기준으로 정렬 후 특정 값 이상의 인포에 대해서만 처리를 하려 했으나 최악의 경우 앞서 언급한 것과 같은꼴이 되어 시간초과가 난다.

결국 순회를 하는 방법은 무조건 시간초과가 나기 때문에 이분탐색을 활용하여 특정 값 이상의 갯수만을 구해야 한다.

우선 순회를 하면 안되므로 모든 경우에 대해서 점수들을 저장해야 한다.

예를들어 '자바-백엔드-주니어-치킨'인 경우를 보자.

위의 쿼리에서 나올수 있는 모든 경우는
1. - - - -
2. 자바 - - -
3. - 백엔드 - -
4. - - 주니어 -
5. - - - 치킨
6. 자바 백엔드 - -
7. 자바 - 주니어 -
8. 자바 - - 치킨
9. - 백엔드 주니어 -
10. - 백엔드 - 치킨
11. - - 주니어 치킨
12. 자바 백엔드 주니어 -
13. 자바 백엔드 - 치킨
14. 자바 - 주니어 치킨
15. - 백엔드 주니어 치킨
16. 자바 백엔드 주니어 치킨
총 16가지가 된다.

즉 위의 16가지 경우에 점수를 넣어주면 된다.

그리고 이런 과정을 모든 인포에 대해 실행한다.

그리고 갹 경우를 이분탐색을 하기위해 정렬 해 준다.

그리고 나서 쿼리를 분석하여 쿼리에 해당하는 경우의 점수들에 대하여 이분탐색으로 적절한 위치를 찾아내면 된다.

코드

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

using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    vector<int> score[4][3][3][3];
    string la[4] = {"","cpp","java","python"};
    string ty[3] = {"","backend","frontend"};
    string ca[3] = {"","junior","senior"};
    string fo[3] = {"","chicken","pizza"};
    for(int i=0;i<info.size();i++){
        string str = "";
        vector<string> tmp;
        for(int j=0;j<info[i].size();j++){
            if(info[i][j] == ' '){
                tmp.push_back(str);
                str = "";
                continue;
            }
            str += info[i][j];
        }
        int sc = stoi(str);
        for(int l=0;l<4;l++){
            for(int t=0;t<3;t++){
                for(int c=0;c<3;c++){
                    for(int f=0;f<3;f++){
                        if((l==0||la[l]==tmp[0])&&(t==0||ty[t]==tmp[1])&&(c==0||ca[c]==tmp[2])&&(f==0||fo[f]==tmp[3])){
                            score[l][t][c][f].push_back(sc);
                        }
                    }
                }
            }
        }
    }
    for(int l=0;l<4;l++){
        for(int t=0;t<3;t++){
            for(int c=0;c<3;c++){
                for(int f=0;f<3;f++){
                    sort(score[l][t][c][f].begin(),score[l][t][c][f].end());
                }
            }
        }
    }
    
    for(int i=0;i<query.size();i++){
        string str = "";
        vector<string> tmp;
        for(int j=0;j<query[i].size();j++){
            if(query[i][j] == ' '){
                if(str != "and")
                    tmp.push_back(str);
                str = "";
                continue;
            }
            str += query[i][j];
        }
        int sc = stoi(str);
        
        int a=0;
        if(tmp[0] == "cpp")
            a=1;
        else if(tmp[0] == "java")
            a=2;
        else if(tmp[0] == "python")
            a=3;
        int b=0;
        if(tmp[1] == "backend")
            b=1;
        else if(tmp[1] == "frontend")
            b=2;
        int c=0;
        if(tmp[2] == "junior")
            c=1;
        else if(tmp[2] == "senior")
            c=2;
        int d=0;
        if(tmp[3] == "chicken")
            d=1;
        else if(tmp[3] == "pizza")
            d=2;
        
        int cnt = upper_bound(score[a][b][c][d].begin(),score[a][b][c][d].end(),sc-1)-score[a][b][c][d].begin();
        answer.push_back(score[a][b][c][d].size()-cnt);
    }
    return answer;
}

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