(C++) - 프로그래머스(2021 KAKAO BLIND RECRUITMENT) : 순위 검색

programmers.co.kr/learn/courses/30/lessons/72412?language=cpp

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

이분탐색 문제였습니다.

 

풀이방법

카테고리는 다음과 같습니다.

• 개발언어 : 3가지
• 지원 직군 : 2가지
• 지원 경력 : 2가지
• 소울푸드 : 2가지

1. 4가지의 카테고리가 필요하며 해당 카테고리에 해당하는 점수를 저장하기 위해 4차원 배열을 사용합니다.

 

2. info의 전체를 확인하며 string으로 되어 있는 해당 정보들을 int로 치환해 따로 저장해줍니다. 

 

3. 점수의 오름차순으로 정렬해줍니다.

 

4. query를 하나씩 확인하면서 해당 범위에 맞는 점수를 lower_bound를 이용해 구합니다. 점수가 정렬되어 있기 때문에 query에서 궁금한 점수값 이상을 가지고 있는 info들은 모두 답이 될 수 있습니다. 따라서 처음으로 점수값이 이상이 되었을 때의 index를 구한다면 size () - index까지가 정답임을 알 수 있습니다. 답을 구했으면 answer에 push해줍니다.

 

 

Code

#include <bits/stdc++.h>
using namespace std;

vector <string> split(string input, char delimiter){
    vector <string> result;
    stringstream ss(input);
    string tmp;

    while(getline(ss,tmp,delimiter)) result.push_back(tmp);
    return result;
}

int getLanguageNum(string data){
    if(data == "cpp") return 0;
    if(data == "java") return 1;
    if(data == "python") return 2;
    return 3;
}

int getJobNum(string data){
    if(data == "backend") return 0;
    if(data == "frontend") return 1;
    return 2;
}

int getCareerNum(string data){
    if(data == "junior") return 0;
    if(data == "senior") return 1;
    return 2;
}

int getSoulFoodNum(string data){
    if(data == "chicken") return 0;
    if(data == "pizza") return 1;
    return 2;
}

void sortAll(vector <int> d[3][2][2][2]){
    for(int l = 0; l < 3; l++){
        for(int j = 0; j < 2; j++){
            for(int c = 0; c < 2; c++){
                for(int s = 0; s < 2; s++){
                    sort(d[l][j][c][s].begin(),d[l][j][c][s].end());
                }
            }
        }
    }
}

int getAns(int al, int bl, int aj, int bj, int ac, int bc, int as, int bs,int score, vector <int> d[3][2][2][2]){
    int cnt = 0;
    for(int l = al; l <= bl; l++){
        for(int j = aj; j <= bj; j++){
            for(int c = ac; c <= bc; c++){
                for(int s = as; s <= bs; s++){
                    int size = d[l][j][c][s].size();
                    int idx = lower_bound(d[l][j][c][s].begin(),d[l][j][c][s].end(),score) - d[l][j][c][s].begin();
                    cnt += size - idx;
                }
            }
        }
    }
    return cnt;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    //언어, 지원 직군, 경력구분, 소울푸드
    vector <int> d[3][2][2][2];
    for(int i = 0; i < info.size(); i++){
        vector <string> splitedInfo = split(info[i], ' ');
        int languageNum = getLanguageNum(splitedInfo[0]);
        int jobNum = getJobNum(splitedInfo[1]);
        int careerNum = getCareerNum(splitedInfo[2]);
        int soulFoodNum = getSoulFoodNum(splitedInfo[3]);
        d[languageNum][jobNum][careerNum][soulFoodNum].push_back(stoi(splitedInfo[4]));
    }

    sortAll(d);
    
    for(int i = 0; i < query.size(); i++){
        int al, bl, aj, bj, ac, bc, as, bs;
        vector <string> splitedQeury = split(query[i], ' ');
        int languageNum = getLanguageNum(splitedQeury[0]);
        int jobNum = getJobNum(splitedQeury[2]);
        int careerNum = getCareerNum(splitedQeury[4]);
        int soulFoodNum = getSoulFoodNum(splitedQeury[6]);
        int score = stoi(splitedQeury[7]);
        //'-'
        if(languageNum == 3) al = 0, bl = 2;
        else al = bl = languageNum;

        if(jobNum == 2) aj = 0, bj = 1;
        else aj = bj = jobNum;

        if(careerNum == 2) ac = 0, bc = 1;
        else ac = bc = careerNum;

        if(soulFoodNum == 2) as = 0, bs = 1;
        else as = bs = soulFoodNum;

        
        answer.push_back(getAns(al, bl, aj, bj, ac, bc, as, bs, score, d));
    }
    return answer;
}