프로그래머스 문제 - 선입 선출 스케줄링

프로그래머스 선입 선출 스케줄링 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

cpu에는 여러 개의 코어가 있으며, 코어별로 한 작업을 처리하는데 시간이 다릅니다.
한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행하며, 2개 이상의 코어가 존재할 경우 앞의 코어부터 작업을 처리합니다.
처리해야 할 작업 n개가 주어질 때 마지막 작업을 처리하는 코어의 번호를 return해야 합니다.

문제 풀이

예제를 가지고 하나씩 진행해보면 문제를 좀 더 쉽게 이해할 수 있습니다.
만약 n=6, [1,2,3]으로 예제가 주어진다면
처음 0시간때는 앞에서 순서대로 모든 cpu에 작업을 넣어주어야 하기 때문에 1->2->3순으로 작업을 처리하도록 넣어줍니다.
이에 코어가 수행하는 작업의 수와 작업을 끝낸 수의 합은 3입니다.
1시간이 지나면 1번째 코어가 주어진 작업을 끝내기 때문에 1번 코어에 다시 작업을 처리하도록 넣어줍니다.
이에 코어가 수행하는 작업의 수와 작업을 끝낸 수의 합은 4입니다.
2시간이 지나면 1, 2번째 코어가 주어진 작업을 끝내기 때문에 1->2번 코어에 다시 작업을 처리하도록 넣어줍니다.
여기서 2번째 코어가 수행하는 작업은 6번째 작업이며, n번째로 작업하는 코어의 번호를 찾아야 하기 때문에 정답은 2가 됩니다.
위의 작업을 차례대로 해보면 n값보다 적게 작업을 진행하는 시간의 최대값을 찾아낸 후, 다음 시간에서 차례대로 코어에 작업을 넣어가며 n번째의 작업을 시작하는 코어를 찾으면 된다는 것을 알 수 있습니다.

n값보다 적게 작업을 진행하는 시간의 최대값을 구하기 위해 작업을 진행하는 시간을 기준으로 얼마나 작업을 진행할 수 있는지를 확인하며 이분탐색을 진행해주면 적은 시간으로 원하는 값을 구할 수 있습니다.

이분탐색을 진행하여 구한 시간이 지났을 때의 코어가 수행하는 작업의 수와 작업을 끝낸 수의 합을 구해줍니다.
이후 구한 시간으로부터 1시간이 지났을 때 작업이 끝난 코어에 작업을 차례대로 넣어주며 n번째의 작업을 시작하는 코어의 번호를 구해주면 됩니다.

전체 코드

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> cores) {
    int answer = 0;
    long long time = 0;
    
    //처리해야하는 일의 갯수가 코어보다 적다면 갯수만큼 return;
    if(n - cores.size() <= 0)
    {
        return n;
    }
    
    long long high = 21000000000;
    long long low = 0;
    while(high >= low)	//n값보다 적게 작업을 진행하는 시간의 최대값을 구함
    {
        long long mid = (high+low)/2;
        time = cores.size();
        for(int i = 0; i < cores.size(); i++)
        {
            time += mid / cores[i];
            if(time >= n)
                break;
        }
        
        if(time >= n)
            high = mid - 1;
        else
            low = mid + 1;            
        
    }
    //시간의 최대값을 가졌을 때의 처리량을 구함
    time = cores.size();
    for(int i = 0; i < cores.size(); i++)
    {
        time += high / cores[i];
    }
    //이후 마지막 작업을 처리하는 코어 탐색
    for(int i = 0; i < cores.size(); i++)
    {
        if((high+1) % cores[i] == 0)
            time++;
        if(time == n)
            return i+1;
    }
    
    return answer;
}

출저

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