[프로그래머스/C++] 순위 검색

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 문자열을 잘 나눌줄 알아야 풀 수 있는 문제다.

 

처음에 문제를 보고 단순히 query가 들어올 때 마다 계산을 할 경우 시간초과가 나게 되어있어서 어떻게 풀까 고민을 많이 했다.

 

그러다가 한 사람이 점수를 제외하면 가질 수 있는 경우의 수가 3*2*2*2로 24개 이며, 점수가 100000으로 모든 경우의 수를 구해도 2,400,000이 된다는 것에 착안해 문제를 해결했다.

 

이때 24개의 경우의 수를 표현하기 위해 cpp, java, python 은 각각 0, 8, 16 backend, frontend 는 4, 0 과 같이 이진법처럼 가중치를 두어 24개의 경우를 숫자로 표현했을 때 겹치지 않도록 변환해 주었다.

(서로 다른 영역이 다른 영역에 영향을 주지 않도록 가중치를 정했다)

 

이렇게 각 인원의 경우가 구분되고 점수가 나오면 2차원 벡터에 점수를 저장했다.

 

여기서 특정 점수 이상의 인원이 몇 명있는지 계산하기 위해서 모든 사람의 경우의 수와 점수를 구한 뒤 누적합을 이용해 query에서 해당하는 사람의 수를 뽑을 때는 O(1)로 한번에 답을 알 수 있도록 했다.

 

마지막으로 24개의 경우의 수 중 query에 해당하는 경우의 수가 몇 개인지를 구하기 위해서 문자열을 잘 나눠야 하는데 이 부분을 하드 코딩했다...

 

하드 코딩할 때 주의해야할 점은 "-"를 처리하는 방법이다.

 

예를 들어 cpp, java, python에 해당하는 부분에서 처음에 "-"가 나오면 모든 경우이므로 break하고 다음에 backend, frontend에 해당하는 query를 탐색한다.

 

만약 "-"가 처음에 나오지 않고 cpp, java, python등의 문자가 먼저 나오면 그 뒤에 있는 "-" 는 cpp, java, python에 해당하는 "-"가 아니므로 무시하도록 처리했다.

 

이렇게 쿼리에 해당하는 경우의 수를 구한 뒤 그 경우의 수에서 몇 점 이상인 사람이 얼마나 있는지 누적합을 이용해 return하면 된다.

 

 

 

​

[아이디어 정리]

1. 점수를 제외한 경우의 수는 24 이므로, 이진법처럼 다른 자릿수에 있는 숫자들이 서로 영향을 주지 않는 것처럼 다른 case에 해당하는 문자가 영향을 주지 않게 가중치를 설정해 24개의 경우의 수를 나눈다.
2. 어떤 경우의 수에 해당하는 지 구했으면, 점수에 인원을 +1하고, 모든 인원의 경우의 수와 점수를 구했다면, 누적합을 이용해 경우의 수에 따른 특정 점수 이상의 인원이 몇 명인지 미리 계산한다.
3. query의 문자열을 잘 나누어 경우의 수에 해당하는 인원을 찾아 return 한다.

 

 

 

Code

 

 

#include <string>
#include <vector>
#include <sstream>
using namespace std;
vector<string> split(string str, char a)
{
    stringstream ss(str); 
    string tmp;
    vector<string> v;
    while(getline(ss, tmp, a)) {
        v.push_back(tmp);
    }
    return v;
}

vector<int> newInt(vector<string>ss, vector<int> llV,int deg)
{
    vector<string> sendstr;
    bool isDash=true;
    int sliceIdx=0;
    vector<int> newV;
    if (deg==0){
        for (int i=0; i<ss.size(); i++)
        {
            if (isDash&&ss[i]=="-"){
                sliceIdx=i;
                newV.push_back(0);
                newV.push_back(8);
                newV.push_back(16);
                break;
            }
            if (ss[i]=="cpp"){
                sliceIdx=i;
                newV.push_back(0);
                
                isDash=false;
            }
            else if(ss[i]=="java"){
                sliceIdx=i;
                newV.push_back(8);
                
                isDash=false;
            }
            else if (ss[i]=="python"){
                sliceIdx=i;
                newV.push_back(16);
                
                isDash=false;
            }
        }
    }
    else if (deg==1){
        for (int i=0; i<ss.size(); i++){
            if (isDash&&ss[i]=="-"){
                sliceIdx=i;
                for (int j=0; j<llV.size(); j++){
                    newV.push_back(llV[j]+4);
                    newV.push_back(llV[j]);
                }
                break;
            }
            if (ss[i]=="backend"){
                sliceIdx=i;
                for (int j=0; j<llV.size(); j++){
                    newV.push_back(llV[j]+4);
                }
                isDash=false;
            }
            else if(ss[i]=="frontend"){
                sliceIdx=i;
                for (int j=0; j<llV.size(); j++){
                    newV.push_back(llV[j]);
                }
                isDash=false;
            }
        }
    }
    else if (deg==2){
        for (int i=0; i<ss.size(); i++){
            if (isDash&&ss[i]=="-"){
                sliceIdx=i;
                for (int j=0; j<llV.size(); j++){
                    newV.push_back(llV[j]+2);
                    newV.push_back(llV[j]);
                }
                break;
            }
            if (ss[i]=="junior"){
                sliceIdx=i;
                for (int j=0; j<llV.size(); j++){
                    newV.push_back(llV[j]+2);
                }
                isDash=false;
            }
            else if(ss[i]=="senior"){
                sliceIdx=i;
                for (int j=0; j<llV.size(); j++){
                    newV.push_back(llV[j]);
                }
                isDash=false;
            }
        }
    }
    else if (deg==3){
        for (int i=0; i<ss.size(); i++){
            if (isDash&&ss[i]=="-"){
                sliceIdx=i;
                for (int j=0; j<llV.size(); j++){
                    newV.push_back(llV[j]+1);
                    newV.push_back(llV[j]);
                }
                break;
            }
            if (ss[i]=="chicken"){
                sliceIdx=i;
                for (int j=0; j<llV.size(); j++){
                    newV.push_back(llV[j]+1);
                }
                isDash=false;
            }
            else if(ss[i]=="pizza"){
                sliceIdx=i;
                for (int j=0; j<llV.size(); j++){
                    newV.push_back(llV[j]);
                }
                isDash=false;
            }
        }
    }
    if (deg==3){
        return newV;
    }
    for (int i=sliceIdx+1; i<ss.size(); i++){
        sendstr.push_back(ss[i]);
    }
    return newInt(sendstr,newV,deg+1);
}

int CInt(vector<string> ss)
{
    int a=0;
    if (ss[0]=="cpp")
        a=0;
    else if(ss[0]=="java")
        a=8;
    else
        a=16;
    if (ss[1]=="backend")
        a+=4;
    if (ss[2]=="junior")
        a+=2;
    if (ss[3]=="chicken")
        a+=1;
    return a;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    vector<vector<string>> sV;
    vector<vector<int>>mmm(24,vector<int>(100001,0));
    vector<vector<int>>nu2(24,vector<int>(100001,0));
    for (int i=0; i<info.size(); i++)
    {
        sV.push_back(split(info[i],' '));
    }
    for (int i=0; i<info.size(); i++)
    {
        mmm[CInt(sV[i])][stoi(sV[i][4])]+=1;
    }
    for (int i=0; i<24; i++){
        nu2[i][100000]=mmm[i][100000];
        for (int j=99999; j>=0; j--)
        {
            nu2[i][j]+=nu2[i][j+1]+mmm[i][j];
        }
    }
    vector<int> retV(query.size(),0);
    vector<string> nowStringV;
    for (int i=0; i<query.size(); i++)
    {
        nowStringV=split(query[i],' ');
        int score=stoi(nowStringV[nowStringV.size()-1]);
        vector<int> a(0);
        vector<int> nowIV=newInt(nowStringV,a, 0);
        for (int j=0; j<nowIV.size(); j++){
            retV[i]+=nu2[nowIV[j]][score];         
        }
    }
    return retV;
}

 

---

중간에 query 부분을 하드코딩했더니 엄청 코드가 길어졌다...

정말 이렇게 푸는게 맞을까...?

 

프로그래머스