[구현] 순위 검색 - 2021 KAKAO BLIND RECRUITMENT

해결 방법

정확성 테스트라면 어렵지 않게 통과할 수 있을 것이지만, info, query 벡터에 대해 그대로 2중 for문을 쓴다면 효율성에서 좋은 점수를 받지 못할 것이다.

 

필자는 다음과 같이 4차원 벡터를 선언했다.

vector<int> iv[4][3][3][3];

개발언어 항목, 지원 직군 항목, 경력구분 항목, 소울 푸드에 있는 각 정보를 차례대로 정수로 나타내어서 저장하기 위해  4차원 형태로 만들었다.

cpp/java/python/-
backend/frontend/-
junior/senior/-
chicken/pizza/-

 

'-' 부분에는 나머지 조건에 해당 하는 모든 경우를 넣어주면 된다. 조건이 4개이기 때문에 하나의 조건이라도 반영하지 않는 경우의 수는 15(4C1+4C2+4C3+4C4=15)가 될 것이다.

이 작업을 해두면 조건을 반영하지 않는 모든 경우까지 4차원 벡터에 반영되기 때문에, 문의 조건을 따질 때는 특별한 연산 없이 4차원 벡터에만 접근하면 된다.

 

이 해결 방법의 시간 복잡도는 O(N+M)이 될 것 같다. 필자가 계산한 시간 복잡도가 틀리다면 댓글을 남겨주길 바란다.

 

 

소스 코드

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

vector<int> iv[4][3][3][3];

vector<int> converter(string s) {
    vector<int> v;
    stringstream ss(s);
    string lan, group, exp, food, score;
    ss >> lan >> group >> exp >> food >> score;
    v.push_back((lan=="cpp")?0:(lan=="java")?1:(lan=="python")?2:3);
    v.push_back((group=="backend")?0:(group=="frontend")?1:2);
    v.push_back((exp=="junior")?0:(exp=="senior")?1:2);
    v.push_back((food=="chicken")?0:(food=="pizza")?1:2);
    v.push_back(stoi(score));
    return v;
}

string replace_all(string target, string pattern, string replace_str) {
    int pos;
    while((pos=target.find(pattern))!=-1) target.replace(pos, pattern.length(), replace_str);   
    return target;
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    for(int i=0;i<info.size();i++) {
        vector<int> cv = converter(info[i]);
        
        // 조건을 모두 고려하는 않는 경우
        iv[cv[0]][cv[1]][cv[2]][cv[3]].push_back(cv[4]);
        
        // 조건 1개를 고려하지 않는 경우
        iv[3][cv[1]][cv[2]][cv[3]].push_back(cv[4]);
        iv[cv[0]][2][cv[2]][cv[3]].push_back(cv[4]);
        iv[cv[0]][cv[1]][2][cv[3]].push_back(cv[4]);
        iv[cv[0]][cv[1]][cv[2]][2].push_back(cv[4]);
        
        // 조건 2개를 고려하지 않는 경우
        iv[3][2][cv[2]][cv[3]].push_back(cv[4]);
        iv[3][cv[1]][2][cv[3]].push_back(cv[4]);
        iv[3][cv[1]][cv[2]][2].push_back(cv[4]);
        iv[cv[0]][2][2][cv[3]].push_back(cv[4]);
        iv[cv[0]][2][cv[2]][2].push_back(cv[4]);
        iv[cv[0]][cv[1]][2][2].push_back(cv[4]);
        
        // 조건 3개를 고려하지 않는 경우
        iv[3][2][2][cv[3]].push_back(cv[4]);
        iv[3][2][cv[2]][2].push_back(cv[4]);
        iv[3][cv[1]][2][2].push_back(cv[4]);
        iv[cv[0]][2][2][2].push_back(cv[4]);
        
        // 조건을 모두 고려하지 않는 경우
        iv[3][2][2][2].push_back(cv[4]);     
    }
    
    for(int i=0;i<query.size();i++) {
        int sum=0;
        query[i]=replace_all(query[i], " and", "");
        vector<int> cv = converter(query[i]);
        vector<int> rv = iv[cv[0]][cv[1]][cv[2]][cv[3]];
        for(int j=0;j<rv.size();j++) if(rv[j]>=cv[4]) sum++;
        answer.push_back(sum);
    }
    return answer;
}

 

정확성, 효율성 모두 만점

 

문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/72412