[2021 카카오 블라인드 테스트] 순위 검색 (c++)

https://school.programmers.co.kr/learn/courses/30/lessons/72412

위의 문제에 대한 해설입니다.

 

 

input으로 들어오는 2개의 vector<string>  에서 각 벡터 안 1개의 string들은 총 5가지 유효한 string 정보를 가지고 있다.

 parser를 통해 유효한 5개의 string의 string을 추출한 뒤, 마지막에 위치한 점수에 대한 부분은 stoi() 함수를 통해 숫자로 바꾼다. map 자료구조를 통해 앞선 4개의 string들을 하나로 묶어 key 값으로써 사용하고, stoi()를 통해 정수형으로 바꾼 점수 정보를 value로써 추가한다. 이때 고려할 사항은 query에서는 '-' 라는 문자열이 특수성을 가진다는 것이다.

'-'는 어떤 것이 와도 상관없다는 뜻이다. 이를 뒤집어서 생각해보자.

결국 info에서 들어오는 5가지의 유효한 string 정보들 중 점수값을 제외한 4개는 어떤 query와 매칭될까?

 

ex)   "a b c d"

" a b c d" 

" - b c d"

" a - c d"

........

 

결국 우리가 부분집합의 개수를 구할 때 각 원소를 포함 or 미포함 2가지 경우의 수로 나누어 2^n 으로 개수를 찾는 것처럼

16가지의 경우의 수가 나오고, 이는 bit masking을 통해  0000~ 1111 모든 16가지 경우의 수에 해당하는 문자열을 key로하는 map에 값을 넣어주면 된다.

 

 

이제 'X점 이상' 이라는 문제에 대해 이야기해보자.

모든 info내의 정보를 처리 한 뒤, map의 각 원소에 위치한 vector<int> 자료구조를 sort()

함수로 내림차순 정렬한다. 이는 문제에서 'X점 이상' 이라는 조건이 붙기 때문인데, X점 이상의 값을 찾기 위한

최적의 방식은 아래와 같다.

'자료구조를 내림차순 정렬하고, 처음 X값이 찾아지는 시점 이후의 값들이 모두 X 점 이상이다.'

우리는 개수만 구하면 되기에 아래와 같은 수식으로  X점이상인 값의 개수를 찾을 수 있다.

전체 개수 - lower_bound (처음 X값이 찾아지는 위치) 

 

#include <string>
#include <vector>
#include<map>
#include<algorithm>
using namespace std;
map<string, vector<int> > ma;

//주어진 string에서 유효한 데이터를 split하여 vector<string>에 저장
vector<string> parser(string list, int bit) { //bit: 0이면 info, 1이면 query
    vector<string> ret;
    string tmp;
    int num = 0;
    for (int i = 0; i < list.size(); i++) {
        if (list[i] == ' ') {
            if (bit == 1 && num < 3) {
                num++;
                i += 4;
            }
            ret.push_back(tmp);
            tmp = "";
        }
        else {
            tmp += list[i];
        }

    }
    ret.push_back(tmp);

    return ret;
}

void addPossible(vector<string> tmp) {
    vector<int> ret;

    for (int i = 0; i < 16; i++) {

        string tmp2;
        for (int j = 0; j < 4; j++) {
            tmp2 += (i & (1 << j) ? tmp[j] : "-");
        }

        ma[tmp2].push_back(stoi(tmp[4]));

    }

}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    for (auto inf : info) {
        vector<string> tmp = parser(inf, 0);

        addPossible(tmp);
    }

    for (auto& m : ma) sort(m.second.begin(), m.second.end());  //lower_bound 사용하려면 정렬해야한다.

    for (int k = 0; k < query.size(); k++) {
        answer.push_back(0);
        vector<string> tmp2 = parser(query[k], 1);
        string str;
        for (int j = 0; j < 4; j++) {
            str += tmp2[j];
        }
        int money = stoi(tmp2[4]);
        if (!ma[str].empty()) {
            answer[k] = ma[str].end() - lower_bound(ma[str].begin(), ma[str].end(), money); //lower_bound>> 위치값. 
            //end() - lower_bound >>> money 이상인 값의 개수
        }

    }
    return answer;
}