64★★★★] 카카오 블라인드 / 순위 검색

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

 

각 항목별로 첫 글자가 다르길래

앞글자씩만 따서 문자열로 만들고 숫자 따로 빼서 

map으로 만들어서 비교하려고 했는데.

 

string은 같은데 숫자가 다를 수도 있고, 

모든 걸 포함하는 - 가 있어서 막힘..

---

이진 탐색 

binary search 알고리즘으로 푼다고 한다..

#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

//언어, 지원 직군, 경력구분, 소울푸드
vector <int> d[3][2][2][2];

// input을 delimiter를 구분지어 나눠서 저장
// 	java backend junior pizza 150
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();
                    // score와 같거나 큰 숫자의 위치 return 
                    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;
}

void putInfo(vector<string> info) {

    for (int i = 0; i < info.size(); i++) {
        vector <string> splitedInfo = split(info[i], ' ');
        // python frontend senior chicken 150 
        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]));
    }

}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;

    // info 형식에 맞게 저장
    putInfo(info);
    
    // 정렬
    sortAll(d);

    for (int i = 0; i < query.size(); i++) {
        int al, bl, aj, bj, ac, bc, as, bs;
        
        // and빼고 저장
        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]);
       
       //'-'
        // 범위 지정 lower_bound 사용 
        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;

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

    return answer;
}

 

 

 

풀이를 봐도 모르겠네.

큰일 났구먼

 

 

---

 

https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기

https://codecollector.tistory.com/1000

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