2021 KAKAO Blind - 3. 순위 검색

목차

개요

설명

코드

 

 

개요

이 문제는 효율성까지 평가하는 문제입니다. 쿼리에 (코테 참여 언어, 지원 직군, 지원 경력, 선호하는 소울푸드)를 구분하여 입력 받고 있으며, 다음으로 점수를 입력 받아 해당 점수 이상의 사람이 몇 명 있는지 반환하는 문제입니다.

 

설명

제가 구현한 것은 segment tree를 활용한 것입니다. 점수를 제외한 항목들을 살펴보면 총 24개(322*2)의 조합이 나오게 되는데, 이 조합들 각각에 segment tree를 이용해 점수를 log N 타임에 구할 수 있도록 하였습니다.

 

Query중에 '-'와 같은 wildcard는 해당하는 조합의 segment tree들을 조사한 뒤에 합하면 될 것입니다.

 

예를 들어, ('python', -, 'senior', 'pizza', 100)과 같은 query가 들어올 때를 생각해봅시다. 이는 간단하게 두 개의 segment tree를 조사하면 됩니다.

 

('python', 'backend', 'senior', 'pizza', 100) + ('python', 'frontend', 'senior', 'pizza', 100)

 

 

코드

 

사실 무엇보다 C++에서 문자열 처리가 조금 익숙치 않았던 점이 있네요.

 

문제를 풀고 나면 다른 사람의 풀이를 확인할 수 있는데, 더 깔끔한 코드가 존재합니다. Segment tree보다 C++의 lower_bound를 활용하여 풀면, 시험 중에 segment tree를 구현할 필요가 없으니 더 빠르게 문제를 풀 수 있을 것입니다..!

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
class Tree{
    int node[400000];
    public:
    void Insert(int cur, int left, int right, int index){
        if(left==right){
            node[cur] ++;
            return;
        }
        int mid = (left+right)/2;
        if(index <= mid) Insert(cur*2, left, mid, index);
        else Insert(cur*2+1, mid+1, right, index);
        node[cur] = node[cur*2] + node[cur*2+1];
    }
    int Search(int cur, int left, int right, int start, int end){
        if(left<=start && end <= right){
            return node[cur];
        }

        int mid = (start+end)/2;
        int sum = 0;
        if(left<=mid) sum+= Search(cur*2, left, right, start, mid);
        if(right>mid) sum+= Search(cur*2+1, left, right, mid+1, end);
        return sum;
    }
};
using namespace std;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    Tree* t[24];
    for(int i=0; i<24; i++){
        t[i] = new Tree();
    }
    vector<string> values;
    int previous, current;
    for(auto itr = info.begin(); itr != info.end(); itr++){
        values.clear();
        previous = 0;
        current = itr->find(" ");
        while(current!=string::npos){
            string substring = itr->substr(previous, current-previous);
            values.push_back(substring);
            previous = current+1;
            current = itr->find(" ",previous);
        }
        values.push_back(itr->substr(previous, current-previous));

        int idx = 0;
        switch(values[0][0]){
            case 'c' : idx = 0; break;
            case 'j' : idx = 8; break;
            case 'p' : idx = 16; break;
        }
        if(values[1][0]=='f') idx +=4;
        if(values[2][0]=='s') idx +=2;
        if(values[3][0]=='p') idx +=1;
        int score = stoi(values[4]);
        t[idx]->Insert(1,0,100000,score);
    }

    for(auto itr = query.begin(); itr != query.end(); itr++){
        previous = 0;
        current = itr->find(" ");
        char condition[4];
        int score;
        for(int i=0; i<7; i++){
            string substring = itr->substr(previous, current-previous);
            previous = current+1;
            current = itr->find(" ",previous);
            if(i%2==1) continue;
            condition[i/2] = substring[0];
        }
        score = stoi(itr->substr(previous, current-previous));
        int sum=0;
        for(int i=0; i<24; i++){
            if(condition[0] == 'c' && !(i<8)) continue;
            if(condition[0] == 'j' && !(i>=8 && i<16)) continue;
            if(condition[0] == 'p' && !(i>=16)) continue;
            if(condition[1] == 'b' && !((i & 4) ==0)) continue;
            if(condition[1] == 'f' && !((i & 4) ==4)) continue;
            if(condition[2] == 'j' && !((i & 2) ==0)) continue;
            if(condition[2] == 's' && !((i & 2) ==2)) continue;
            if(condition[3] == 'c' && !((i & 1) ==0)) continue;
            if(condition[3] == 'p' && !((i & 1) ==1)) continue;
            sum += t[i]->Search(1, score, 100000, 0, 100000);
        }
        answer.push_back(sum);
    }
    return answer;
}