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

문제 링크 : 순위 검색

---

참고, 참고

[문제 접근]

query와 info를 돌면서 전체를 카운트 해주면 쉽게 정확성을 만족할 수 있다. 하지만 이 방법으로는 효율성은 통과할 수 없다.

나는 어떤식으로 접근해야할 지 몰라서 다른 사람이 푼 방식을 참고해서 풀었다.

• 언어: 3가지
• 분야: 2가지
• 경력: 2가지
• 음식: 2가지
• 점수: 정수형

문제에서 위와 같은 조건을 가지고 있으므로 인덱스로 표현할 수 있는 4가지를 이용해 4차원 vector를 만들고 해당 인덱스에 값으로 점수를 넣어서 저장한다.
ex) arr[0][1][1][0] = 150 -> 언어는 cpp, 분야는 frontend, 경력은 senior, 음식은 chicken 점수는 150점인 정보이다.

이후 query를 돌면서 탐색 분야가 - 이라면 전체를 탐색해준다.
ex) 언어가 cpp면 0~0을 탐색하고 -면 0~2를 탐색

또 조건에 맞는 배열을 탐색하며 조건 점수보다 높은 것들을 찾아서 cnt에 더해줄 때 배열을 0부터 탐색하며 찾게되면 O(n)이 걸려 총 O(n^2)이 걸리므로 시간초과가 발생한다.

따라서 미리 점수에 따라 오름차순으로 정렬하고 이분탐색을 이용해 조건 점수보다 같거나 높은 값이 나오는 인덱스를 찾고 배열 크기에서 인덱스를 빼주면 조건 점수보다 같거나 높은 조건들의 총 개수를 구할 수 있게된다.

[소스 코드]

#include <bits/stdc++.h>
using namespace std;
vector<int> arr[3][2][2][2];

vector<int> infoParser(string s) {
    vector<int> result;
    int index=0;
    for(int i=0 ; i<s.size() ; i++) {
        if(s[i]==' ') {
            string temp = s.substr(index, i-index);
            index = i+1;
            int add;
            if(temp == "cpp" || temp == "backend" || temp == "junior" || temp == "chicken") add=0;
            else if(temp == "python") add =2;
            else add =1;
            result.push_back(add);
        }
    }
    result.push_back(stoi(s.substr(index)));
    
    return result;
}

vector<string> queryParser(string s) {
    vector<string> result;
    int index=0;
    for(int i=0 ; i<s.size() ; i++) {
        if(s[i]==' ') {
            string temp = s.substr(index, i-index);
            index = i+1;
            result.push_back(temp);
        }
    }
    result.push_back(s.substr(index));
    
    return result;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    // info 파싱해서 배열에 저장
    for(string s : info) {
        vector<int> temp = infoParser(s);
        arr[temp[0]][temp[1]][temp[2]][temp[3]].push_back(temp[4]);
    }
    
    // 이분탐색을 위해 정렬
    for(int a=0 ; a<3 ; a++) {
        for(int b=0 ; b<2 ; b++) {
            for(int c=0 ; c<2 ; c++) {
                for(int d=0 ; d<2 ; d++) {
                    sort(arr[a][b][c][d].begin(), arr[a][b][c][d].end());
                }
            }
        }
    }
    
    // query 파싱해서 조건에 맞는 값 더해주기
    for(string s : query) {
        vector<string> temp = queryParser(s);
        
        // 탐색 범위 설정
        int starta, enda, startb, endb, startc, endc, startd, endd;
        
        if(temp[0]=="cpp") starta=enda=0;
        else if(temp[0]=="java") starta=enda=1;
        else if(temp[0]=="python") starta=enda=2;
        else starta=0, enda=2;
        
        if(temp[2]=="backend") startb=endb=0;
        else if(temp[2]=="frontend") startb=endb=1;
        else startb=0, endb=1;
        
        if(temp[4]=="junior") startc=endc=0;
        else if(temp[4]=="senior") startc=endc=1;
        else startc=0, endc=1;
        
        if(temp[6]=="chicken") startd=endd=0;
        else if(temp[6]=="pizza") startd=endd=1;
        else startd=0, endd=1;
        
        int score = stoi(temp[7]);
        
        // 설정해준 범위를 탐색하면서 나온 값들을 answer에 push
        int cnt=0;
        for(int a=starta ; a<=enda ; a++) {
            for(int b=startb ; b<=endb ; b++) {
                for(int c=startc ; c<=endc ; c++) {
                    for(int d=startd ; d<=endd ; d++) {
                        // arr[a][b][c][d]를 전부 돌면서 점수를 체크하면 시간초과
                        // 따라서 score보다 같거나 높은 점수들의 개수를 찾음 == 시작점이라고 가정
                        
                        int index = lower_bound(arr[a][b][c][d].begin(), arr[a][b][c][d].end(), score) - arr[a][b][c][d].begin(); // 시작점의 인덱스를 가져옴
                        // 시작점이 없다면 배열의 끝인덱스보다 1큰 인덱스가 나옴
                        cnt += (arr[a][b][c][d].size()-index); // 배열 전체 개수에서 시작점의 인덱스를 빼면 시작점부터 끝까지의 개수가 나옴
                    }
                }
            }
        }
        
        answer.push_back(cnt);
    }
    
    return answer;
}