순위 검색

프로그래머스 순위 검색 풀이

문제설명

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

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

인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.

예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.

코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?

문의사항에는 “-”을 표시도 사용할 수 있다. “-”는 해당 조건은 신경쓰지 않아도 되는 것을 의미한다. 즉, 개발언어항목에 “-”표시가 오면 언어에 상관없이 나머지 조건으로 찾겠다는 의미이다.

제한사항

• 1 ≤ 지원자수 ≤ 50,000
• 1 ≤ 쿼리 ≤ 100,000

모든 지원자를 vector로 관리하고, 이분 탐색으로 쿼리를 찾으면 빠듯하게? 시간안에 동작한다.

$O(5 * 10^4 * 10^5)$

해결과정

구조체를 통해 지원자 전체를 관리한다. 이를 정렬한 뒤, 이분탐색으로 원하는 범위를 찾는다.

다만 “-”가 나올때는 관련해서 찾아야하는 경우의 수를 모두 구하여 더하는 방식을 선택했다.

예를 들어 모든 조건이 “-”이고, 점수가 100점이상을 찾으면 {cpp, backend, junior, chicken} 부터 {python, frontend, senior, pizza}까지 총 24가지 경우의 수를 모두 구한뒤 값을 더했다.

소스코드

#include <bits/stdc++.h>

using namespace std;

struct apply{
    int lang; //0:cpp, 1:java, 2:python
    int type; //0:backend, 1:frontend
    int career; //0:주니어, 1:시니어
    int food; //0:chickend, 1: pizza
    int score; // 코딩테스트 점수
};
unordered_map<string, int> mmap;
void Init(){
    mmap["cpp"] = mmap["backend"] = mmap["junior"] = mmap["chicken"] = 0;
    mmap["java"] = mmap["frontend"] = mmap["senior"]  = mmap["pizza"] = 1;
    mmap["python"] = 2;
}
bool compare(const struct apply& a, const struct apply& b){
    if(a.lang != b.lang) return a.lang < b.lang;
    if(a.type != b.type) return a.type < b.type;
    if(a.career != b.career) return a.career < b.career;
    if(a.food != b.food) return a.food < b.food;
    return a.score < b.score;
}

vector<string> stringsplit(const string& in){
    istringstream iss(in);
    string token;
    vector<string> tokens;
    while(iss >> token){
        tokens.push_back(token);
    }
    return tokens;
}
vector<struct apply> db;

bool check(const struct apply& c, const struct apply& test){
    if(c.score > test.score || c.lang != test.lang || c.type != test.type || c.career != test.career || c.food != test.food) return false;
    return true;
}
int cal(struct apply& input){
    int left = lower_bound(db.begin(), db.end(), input, compare) - db.begin();
    if(!check(input, db[left])) return 0;
    int l = left;
    int r = db.size() - 1;
    while(l < r){
        const int mid = l + (r - l)/2;
        check(input, db[mid]) ? l = mid + 1 : r = mid;
    }
    if(l == db.size() - 1 && check(input, db[l])) l++;
    return l - left;
}

vector<int> solution(vector<string> info, vector<string> query) {
    Init();
    for(const string& in : info){
        vector<string> input = stringsplit(in);
        struct apply tmp = {mmap[input[0]], mmap[input[1]], mmap[input[2]], mmap[input[3]], stoi(input[4])};
        db.push_back(tmp);
    }
    sort(db.begin(),db.end(),compare);
    vector<int> ans;
    for(const string& in : query){
        vector<string> input = stringsplit(in);
        vector<struct apply> tmp;
        vector<int> lang, type, career, food;
        int score = stoi(input[7]);
        if(input[0] != "-") lang.push_back(mmap[input[0]]);
        else lang = {0, 1, 2};
        if(input[2] != "-") type.push_back(mmap[input[2]]);
        else type = {0, 1};
        if(input[4] != "-") career.push_back(mmap[input[4]]);
        else career = {0, 1};
        if(input[6] != "-") food.push_back(mmap[input[6]]);
        else food = {0, 1};
        for(int& l : lang){
            for(int& t : type){
                for(int& c: career){
                    for(int& f : food){            
                        tmp.push_back({l, t, c, f, score});
                    }
                }
            }
        }
        int sum = 0;
        for(struct apply& para : tmp){
            sum += cal(para);
        }
        ans.push_back(sum);
    }
    return ans;
}

배운점

처음에 구조체에서 언어, 직군, 경력, 소울푸드를 문자열로 관리하니 효율성에서 2개는 맞고, 2개는 시간초과가 났다. 전체적인 알고리즘의 시간복잡도는 빠듯해도, 안으로 들어올거라 생각해서 어디서 생각보다 더 큰 시간이 발생했는지 찾았다. 문제는 문자열이었다. 구조체에서 문자열이 많이쓰이다보니, 구조체를 생성하면서 복사하는 과정?으로도 생각보다 많은 리소스는 사용했다. 문자열을 정수형으로 변환하여 해결했다.

또한, 다른 사람의 풀이를 보니 unordered_map을 이용하여 해결하는 것이 가장 효율적인 방법같다. 나는 효율성 테스트에서 평균적으로 500ms가 나오고, 가장 큰 값은 약 700ms가 나오는데 해당 풀이는 안정적이게 모두 300 ~ 400ms이하가 나온다.

간단하게 그 알고리즘에 대해 설명하면, 자료구조는 unordered_map<string, vector> 형식으로, string = query 역할, vector는 query에 대한 score 리스트를 의미한다.우선 info를 순회하면서 각 정보를 넣는다. 정보를 넣을 때, ‘-’인 경우도 넣는다. 즉 “java backend junior pizza”도 넣지만 “- backend junior pizza”등 다른 경우도 넣는다. 최종적으로 하나의 정보당 map에 16개를 넣게되고, 마지막은 “- - - -” 이다.

이제 query를 순회하며 각 점수리스트에서 이분탐색을 진행한다.