[BinarySearch, DFS] (프로그래머스 Lv 2) 순위 검색

문제

• 문제 링크
• 문제 설명: 지원자가 지원서에 입력한 4가지의 정보(개발언어, 직군, 경력, 소울푸드)와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 반환하는 함수 작성
• 입력
  • info 배열의 크기는 1 이상 50,000 이하
  • 개발언어는 cpp, java, python 중 하나
  • 직군은 backend, frontend 중 하나
  • 소울푸드는 chicken, pizza 중 하나
  • 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수
  • query 배열의 크기는 1 이상 100,000 이하
  • query의 각 문자열은 "[조건] X" 형식
  • '-' 표시는 해당 조건을 고려하지 않겠다는 의미
  • X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미
• 출력: 매 query마다 조건을 만족하는 사람 수를 배열에 담아 반환

info	query	result
["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"]	[1,1,1,1,2,4]

풀이

• query 배열의 크기가 최대 10만이기 때문에 매 쿼리에 info 배열을 순회하는 것은 시간초과가 발생한다. 따라서 O(logN) 으로 조건을 만족하는 사람을 찾도록 info 배열을 전처리 해주어야 한다.
• logN 의 시간으로 탐색하는 방법은 이진 탐색이 있다. 이진 탐색은 탐색 대상이 오름차순으로 정렬되었음을 가정한다.
• 4가지 지원자의 정보로 조합 가능한 조건들은 최대 (3+1) * (2+1) * (2+1) * (2+1) = 4 * 3 * 3 * 3 = 108가지이다. 1을 더한 것은 '-'을 포함한 것이다.
• map<string, vector<int>> 자료형을 이용해서 108가지의 조건 각각을 키로 가지고 조건에 해당되는 지원자의 점수를 값으로 가지게 하면 정렬 후 이진 탐색으로 원소의 위치를 알아내서 컨테이너 끝하고 오프셋으로 사람 수를 계산할 수 있게 된다.
  • 시간 절약을 위해 unordered_map 을 활용하기로 했다.

#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <unordered_map>
#include <algorithm>
using namespace std;

// 각 조건과 해당되는 점수 목록을 저장할 자료구조
unordered_map<string, vector<int>> m;

// 지원자 정보로 가능한 조건을 조합
void dfs(int pos, vector<string>& key, int& score, string s) {
    if (pos == key.size()) {
        m[s].push_back(score); // 생성된 조건마다 지원자의 점수 저장
        return;
    }
    dfs(pos + 1, key, score, s + key[pos]);
    dfs(pos + 1, key, score, s + "-");
}

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    vector<string> key(4);
    int score;
    for (auto& i : info) {
        istringstream iss(i);
        iss >> key[0] >> key[1] >> key[2] >> key[3] >> score;
        dfs(0, key, score, ""); // 가지고 있는 조건들로 가능한 조건 조합을 생성
    }
    
    for (auto it = m.begin(); it != m.end(); it++)
        sort(it->second.begin(), it->second.end()); // 각 조건마다 지원자의 점수들을 오름차순 정렬
    
    for (auto& q : query) {
        istringstream iss(q);
        string tmp; // and
        iss >> key[0] >> tmp >> key[1] >> tmp >> key[2] >> tmp >> key[3] >> score;
        auto it = m.find(key[0] + key[1] + key[2] + key[3]);
        if (it == m.end()) answer.push_back(0); // 없는 조건이면 0명
        else { // 있는 조건이면 이진 탐색으로 오프셋 계산
            // lower_bound는 score보다 이상인 값들 중 가장 작은 값(하한)의 위치를 반환
            auto vit = lower_bound(it->second.begin(), it->second.end(), score);
            int num_applicants = it->second.end() - vit;
            answer.push_back(num_applicants);
        }
    }
    return answer;
}