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

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

프로그래머스

 

아니 이번 문제 이거 level 2 맞아?

level 3 느낌인데?..... 

 

생각의 흐름

우선 매번 조건을 검색하기에는 최대 50000 * 100000 = 50억 이기 때문에, 제한시간안에 해결할수가 없다...

 

따라서 입력값들을 잘 정렬하여 이진탐색으로 끝내야 겠다는 생각을 했다!

(ps. 처음에 잘못 푼 방식으로는 User라는 class를 만들어 정렬하고 해서 해볼려 했는데... 실패했다....)

 

우선 다음과 같이 MAP을 생성하고, 각 값에 대한 index값을 지정해두자.

unordered_map<string, int> MAP;

MAP["-"] = 0;
MAP["cpp"] = 1;
MAP["java"] = 2;
MAP["python"] = 3;
MAP["backend"] = 1;
MAP["frontend"] = 2;
MAP["junior"] = 1;
MAP["senior"] = 2;
MAP["chicken"] = 1;
MAP["pizza"] = 2;

위와 같이 index를 지정하면, 예를 들어 "- - - -"의 경우 "0 0 0 0"의 경우가 된다.

 

이후 vector<int> vec[4][3][3][3] 이라는 벡터 배열을 구현할 것 이다.

출처 - https://youtu.be/dy4n61P8SPs

이렇게 만든 벡터 배열에서 해당되는 모든 경우에 점수를 추가해주면 된다!

여기서 해당되는 모든 경우란? 무엇일까?

 

예를 들어 python frontend senior chicken 210 이 input이라 해보자.

선택의 유무에 따라 경우의 수가 나뉘어 진다.

python이 추가되는 경우와, 추가되지 않는 경우

frontend가 추가되는 경우와, 추가되지 않는 경우

senior가 추가되는 경우와, 추가되지 않는 경우

chicken이 추가되는 경우와, 추가되지 않는 경우

 

즉 2*2*2*2 에 해당되는 모든 경우에 210점을 추가해두면 된다. 경우는 다음과 같다.

 

python frontend senior chicken

- frontend senior chicken

python - senior chicken

python frontend - chicken

python frontend senior -

... (중략) ...

- - - -

 

즉, "-"이 입력된 경우도 고려해야하기 때문이다.

따라서 다음과 같이 비트마스킹을 통하여 조합을 구한다.

int arr[4] = {MAP[language], MAP[part], MAP[career], MAP[food]};

for(int i = 0; i < (1 << 4); i++) {
    int idx[4] = {0,};
    for(int j = 0; j < 4; j++) {
        if(i & (1 << j)) {
            idx[j] = arr[j];
        }
    }
    vec[idx[0]][idx[1]][idx[2]][idx[3]].push_back(score);
}

비트마스킹으로 조합을 구하면서 해당되는 경우 전부 score를 추가해 준다.

 

이후 query가 들어올 때 이에 맞는 vector를 찾아 해당 벡터에서 이분탁색을 수행하면 된다!

 

나의 코드

#include <bits/stdc++.h>

using namespace std;

unordered_map<string, int> MAP;
vector<int> vec[4][3][3][3];

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    MAP["-"] = 0;
    MAP["cpp"] = 1;
    MAP["java"] = 2;
    MAP["python"] = 3;
    MAP["backend"] = 1;
    MAP["frontend"] = 2;
    MAP["junior"] = 1;
    MAP["senior"] = 2;
    MAP["chicken"] = 1;
    MAP["pizza"] = 2;
    
    for(auto e : info) {
        stringstream ss(e);
        string language, part, career, food;
        int score;
        
        ss >> language >> part >> career >> food >> score;
        
        int arr[4] = {MAP[language], MAP[part], MAP[career], MAP[food]};
        
        for(int i = 0; i < (1 << 4); i++) {
            int idx[4] = {0,};
            for(int j = 0; j < 4; j++) {
                if(i & (1 << j)) {
                    idx[j] = arr[j];
                }
            }
            vec[idx[0]][idx[1]][idx[2]][idx[3]].push_back(score);
        }
    }
    
    for(int a = 0; a < 4; a++) {
        for(int b = 0; b < 3; b++) {
            for(int c = 0; c < 3; c++) {
                for(int d = 0; d < 3; d++) {
                    sort(vec[a][b][c][d].begin(), vec[a][b][c][d].end());
                }
            }
        }
    }
    
    for(auto e : query) {
        stringstream ss(e);
        string a, b, c, d, temp;
        int score;
        
        ss >> a >> temp >> b >> temp >> c >> temp >> d >> score;
        auto& slist = vec[MAP[a]][MAP[b]][MAP[c]][MAP[d]];
        
        vector<int>::iterator low = lower_bound(slist.begin(), slist.end(), score);
        answer.push_back(slist.end() - low);
    }
    
    return answer;
}