[C++] 프로그래머스 선입 선출 스케줄링

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

프로그래머스

풀이

문제를 보고 '입국심사' 문제가 생각나서 이진 탐색을 떠올렸다.

 

일반적인 이진 탐색과는 달리 '파라메트릭 서치' 라는 알고리즘을 사용한다.

 

이 문제에서는, mid 시간 이전에 수행한 작업량(workCnt)과 현재 시간에 수행한 작업량(curWorkCnt)을 사용해 left, right 변수를 조정한다.

 

조건 1. workCnt >= n 인 경우 mid시간 이전에 수행한 작업량이 현재 시간의 작업량을 더하지 않고도 원하는 작업량보다 크므로 오른쪽 범위를 줄인다. 이 부분이 헷갈렸는데, '현재 시간에는 무조건 작업한 것이 있어야 한다' 라고 이해하면 될것같다. 현재 시간에 작업한 것이 없다면 답은 현재 시간에서 구해지는 것이 아니기 때문이다.

 

조건 2. 수행한 작업 총량이 해야하는 작업량(n)보다 작다면 left 범위를 늘려준다.

 

조건 3. 그 외의 경우 (현재 수행한 작업이 존재하고 작업의 총량이 해야하는 작업량보다 크거나 같다), 답을 구할 수 있는 구간이므로 답을 구한다.

#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;
    
int solution(int n, vector<int> cores) {
    ll answer = 0;
    int num_cores = cores.size();
    if (n <= num_cores) return n;
    // 시간이 주어질 때 몫 만큼 해결
    // 2개 코어, 10000시간, 50000개 작업
    // n / cores.size() * max time
    ll left = 1;
    ll right = *max_element(cores.begin(), cores.end()) * n / cores.size();
    ll mid = 0;

    while (left <= right) {
        mid = (left + right) / 2;
        int workCnt = num_cores;
        int currWorkCnt = 0;
        
        for (int i=0; i<num_cores; i++) {
            workCnt += (mid / cores[i]);
            
            if (mid % cores[i] == 0) {
                workCnt--;
                currWorkCnt++;
            }
        }
        
        int totalWork = workCnt + currWorkCnt;
        
        if (workCnt >= n)
            right = mid - 1;
        else if (totalWork < n)
            left = mid + 1;
        else {
            for (int i=0; i<num_cores; i++) {
                if (mid % cores[i] == 0) {
                    workCnt++;
                }
                if (workCnt == n) {
                    return i+1;
                }
            }
        }
        
    }

    return answer;
}