[프로그래머스] 선입 선출 스케줄링 / 이분탐색, binary search / C++ 풀이

문제 링크

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

프로그래머스

 

풀이 전략

각 코어가 작업을 받을 수 있는 시각인지 확인하며 n개를 처리할 때까지 반복문을 돌리면 시간 초과가 난다. 일의 개수는 최대 50,000이고 코어의 수는 최대 10,000 개다. 최악의 경우 5억( = 50,000 * 10,000)회의 반복문이 돌기 때문에 효율성 테스트를 통과할 수 없다. 따라서 더 효율적인 방법을 생각해야 한다.

 

문제에서 '한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행' 한다고 한다. 그러므로 코어들은 가장 효율적으로 작업을 수행하고 있다. 

어떤 시간 동안 코어들이 열심히 작업을 수행하여 X개의 작업을 처리할 수 있다고 하자. 시간이 많이 주어진다면 X가 커질것이고 적게 주어진다면 X는 작아질 것이다. 따라서 n개의 작업을 처리하는 시간은 이분탐색으로 찾을 수 있다.

이렇게 찾은 시간을 t라고 하자. 마지막 작업을 수행하는 코어에 t시각에 작업이 들어갈 것이다.

 

(t-1) 시각까지 처리한(코어에 등록된) 작업의 수를 전체 작업 수 n에서 빼면 t 시각에 남아있는 작업 수를 알 수 있다. 코어는 앞선 순서로 작업을 받으므로 코어의 배열을 앞에서부터 보면서 t 시각에 작업을 받을 수 있는 코어인지 확인한다. 작업을 받을 수 있다면 남은 작업의 수를 하나씩 차감하고 0이 된다면 그 코어를 답으로 반환하면 된다.

 

코드

#include <vector>
#include <limits.h>
#define INF (999999)
using namespace std;

int solution(int n, vector<int> cores) {
    int answer;
    
    int coreCnt = cores.size();
    if(n <= coreCnt) {
        return n;
    }
    
    /*
    주어진 mid 시간동안 끝낼 수 있는 job의 수
    job을 n개를 할 수 있는 시간 중 최소를 구하여 time으로 정한다.
    time 시각에 마지막 작업이 등록된다.
    */
    int left = 0;
    int right = INF;
    int time = INF;
    while(left <= right) {
        int mid = (left + right) / 2;
        
        int jobCnt = coreCnt;
        for(int t : cores) {
            jobCnt += (mid / t);
        }
        
        if(jobCnt >= n) {
            right = mid - 1;
            time = min(time, mid);
        }
        else { //jobCnt < n
            left = mid + 1; 
        }
    }
    
    /*
    registered count : 등록된 작업 개수
    time의 직전 시각까지 등록된 작업 개수를 구함.
    */
    int regCnt = coreCnt;
    for(int t : cores) {
        regCnt += (time - 1) / t;
    }
    
    int jobCnt = n - regCnt; /*실제로 남은 작업 수*/
    int coreIdx = 0;
    while (true) {/*마지막 작업이 들어갈 코어를 구함.*/
        if(time % cores[coreIdx % coreCnt] == 0) {
            jobCnt--;
        }
        
        if(jobCnt == 0) {
            answer = coreIdx + 1;
            break;
        }
        coreIdx++;
    }
        
    return answer;
}