[알고리즘] 쿼리 알고리즘

문제 출처 : 프로그래머스 순위 검색 lv2

1. 문제 개요

1) Problem

2) 입출력 예시

• "java and backend and junior and pizza 100"
  -> java로 코딩테스트를 봤으며, backend 직군을 선택했고 junior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 100점 이상 받은 지원자는 1명 입니다.

info 배열의 길이가 최대 50,000 그리고 query 배열의 크기가 최대 100,000 이므로 이 문제에서는 시간 초과를 필수적으로 고려해야한다.

2. Solution

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

using namespace std;

// 주어진 문자열을 공백을 기준으로 나누어 벡터에 저장하는 함수
vector<string> data_parse(string data) {
    vector<string> ret;
    string tmp = "";

    for (auto c : data) {
        if (c == ' ') {
            // "and"가 아닌 경우에만 저장
            if (tmp != "and")
                ret.push_back(tmp);
            tmp = "";
        }
        else
            tmp += c;
    }

    // 마지막 남은 문자열도 저장
    ret.push_back(tmp);
    return ret;
}

// 주어진 정보(info)와 질의(query)에 대한 답을 계산하는 함수
vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;

    // 정보를 저장하는 맵(database)
    map<string, vector<int>> db;

    // 1. 주어진 정보를 기반으로 개발자 정보 맵을 생성
    for (auto inf : info) {
        // 주어진 정보를 공백을 기준으로 나누어 키와 값을 저장
        vector<string> key = data_parse(inf);

        // 모든 가능한 조합에 대해 정보를 맵에 저장
        for (int i = 0; i < 16; ++i) {
            string tmp = "";
            for (int j = 0; j < 4; ++j) {
                // 비트마스크를 이용하여 "-"를 포함한 모든 가능한 키 생성
                tmp += (i & (1 << j)) ? key[j] : "-";
            }
            // 키에 대한 정보(점수)를 맵에 추가
            db[tmp].push_back(stoi(key[4]));
        }
    }

    // 2. 맵 내의 각 벡터(점수)를 내림차순 정렬
    for (auto& iter : db)
        sort(iter.second.begin(), iter.second.end());

    // 3. 주어진 질의에 대한 답을 계산
    for (auto q : query) {
        // 질의를 공백을 기준으로 나누어 키와 값을 저장
        vector<string> key = data_parse(q);

        // 검색할 맵의 키 생성
        string k = key[0] + key[1] + key[2] + key[3];

        // 해당 키에 대한 정보(점수) 벡터 가져오기
        vector<int> res = db[k];

        // 이진 탐색을 이용하여 주어진 점수 이상인 개발자 수 계산
        int cnt = res.end() - lower_bound(res.begin(), res.end(), stoi(key[4]));

        // 4. 답 벡터에 개발자 수 추가
        answer.push_back(cnt);
    }

    // 계산된 답 벡터 반환
    return answer;
}

int main() {
    // 테스트 케이스 실행
    solution({ "java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50" },
    { "java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150" });

    // 프로그램 종료
    return 0;
}