[프로그래머스 Level 2] 순위 검색 (2021 카카오 기출)

🖊️ 문제

순위 검색  

 

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.

• 코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
• 지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
• 지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
• 선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.

인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.

• 코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
• backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
• 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
• 코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?

 

즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.

* [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?

지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때,
각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

🖥️ 코드

#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <map>

using namespace std;

vector<int> solution(vector<string> info, vector<string> query) 
{
    vector<int> answer;
    vector<int> db[3][2][2][2];
    map<string, int> m;
    m["-"] = -1;
    m["cpp"] = 0;
    m["java"] = 1;
    m["python"] = 2;
    m["backend"] = 0;
    m["frontend"] = 1;
    m["junior"] = 0;
    m["senior"] = 1;
    m["chicken"] = 0;
    m["pizza"] = 1;
    
    for(int i = 0; i < info.size(); i++)
    {
        stringstream ss(info[i]);
        string a, b, c, d, e;
        ss >> a >> b >> c >> d >> e;
        db[m[a]][m[b]][m[c]][m[d]].push_back(stoi(e));
    }
    
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 2; j++)
            for(int k = 0; k < 2; k++)
                for(int l = 0; l < 2; l++)
                    sort(db[i][j][k][l].begin(), db[i][j][k][l].end(), greater<int>());
    
    for(int i = 0; i < query.size(); i++)
    {
        stringstream ss(query[i]);
        string a, b, c, d, e, dummy;
        int la, pos, cr, fd, score, res = 0;
        
        ss >> a >> dummy >> b >> dummy >> c >> dummy >> d >> e;
        la = m[a], pos = m[b], cr = m[c], fd = m[d], score = stoi(e);
        
        for(int j = 0; j < 3; j++)
        {
            if(la != -1 && la != j) continue;
            for(int k = 0; k < 2; k++)
            {
                if(pos != -1 && pos != k) continue;
                for(int l = 0; l < 2; l++)
                {
                    if(cr != -1 && cr != l) continue;
                    for(int m = 0; m < 2; m++)
                    {
                        if(fd != -1 && fd != m) continue;
                        for(int n = 0; n < db[j][k][l][m].size(); n++)
                        {
                            if(db[j][k][l][m][n] >= score) res++;
                            else break;
                        }
                    }
                }
            }
        }
        answer.push_back(res);
    }
    
    return answer;
}

 

🤔 나의 생각

조건을 고려하지 않는 -를 똑똑하게 처리해 보려고 노력했는데 생각이 안 나서 그냥 중첩 for를 돌렸다...

조건을 조합하는 경우의 수가 적어서 중첩 for를 사용했지만 조금 더 스마트한 방법이 필요한 것 같아 다른 사람의 풀이를 참고해서 새로 풀어봤다.

 

비트 연산자 사용 풀이

비트 연산자로 -가 포함되는 모든 경우의 수를 계산해서 미리 db 벡터에 넣어주는 코드이다.

 

예를 들어 지원자 정보 java backend junior pizza를 파싱 하면

[2, 1, 1, 2]이 된다.여기서 라인 34의 j가 1일 때를 생각해 보면, 1은 2진수로 0001로 k for문을 돌며 -가 포함되는 조건을 [2, 0(-), 0(-), 0(-)] db에 저장하게 된다.

#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
#include <map>

using namespace std;

vector<int> solution(vector<string> info, vector<string> query)
{
    vector<int> answer;
    vector<int> db[4][3][3][3];
    map<string, int> m;
    m["-"] = 0;
    m["cpp"] = 1;
    m["java"] = 2;
    m["python"] = 3;
    m["backend"] = 1;
    m["frontend"] = 2;
    m["junior"] = 1;
    m["senior"] = 2;
    m["chicken"] = 1;
    m["pizza"] = 2;

    for (int i = 0; i < info.size(); i++)
    {
        stringstream ss(info[i]);
        string a, b, c, d;
        int score;

        ss >> a >> b >> c >> d >> score;
        vector<int> v = { m[a], m[b], m[c], m[d] };

        for (int j = 0; j < 16; j++)
        {
            vector<int> idxs(4, 0);
            for (int k = 0; k < 4; k++)
                if (j & (1 << k))
                    idxs[k] = v[k];

            db[idxs[0]][idxs[1]][idxs[2]][idxs[3]].push_back(score);
        }
    }

    for (int i = 0; i < 4; i++)
        for (int j = 0; j < 3; j++)
            for (int k = 0; k < 3; k++)
                for (int l = 0; l < 3; l++)
                    sort(db[i][j][k][l].begin(), db[i][j][k][l].end(), less<int>());

    for (int i = 0; i < query.size(); i++)
    {
        stringstream ss(query[i]);
        string a, b, c, d, dummy;
        int res = 0, score;

        ss >> a >> dummy >> b >> dummy >> c >> dummy >> d >> score;
        vector<int>& v = db[m[a]][m[b]][m[c]][m[d]];

        auto iter = lower_bound(v.begin(), v.end(), score);
        answer.push_back(v.end() - iter);
    }

    return answer;
}

중요한 건 -가 포함되는 조건을 db에 다 넣었기 때문에 단순 for문을 돌며 x점 이상을 받은 사람들의 수를 구하면 시간 초과가 나는 듯하다. 많은 사람들이 정답 도출을 위해 이진 탐색을 이용했다. 이진 탐색에서 파생된 lower_bound는 찾는 값 이상이 처음으로 나오는 원소의 반복자를 반환한다.

 

+ 실제 이진 탐색은 binary_search로 구현되어 있다.

비트 연산자를 이렇게 쓸 수 있음을 배워나갔다~!