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

문제 설명

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.

이 CPU는 다음과 같은 특징이 있습니다.

• CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
• 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
• 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.

처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.

제한 사항

• 코어의 수는 10,000 이하 2이상 입니다.
• 코어당 작업을 처리하는 시간은 10,000이하 입니다.
• 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.

---

입출력 예

n	cores	result
6	[1,2,3]	2

입출력 예 설명

입출력 예 #1
처음 3개의 작업은 각각 1,2,3번에 들어가고, 1시간 뒤 1번 코어에 4번째 작업,다시 1시간 뒤 1,2번 코어에 5,6번째 작업이 들어가므로 2를 반환해주면 됩니다.

풀이)

시간제약이 있어, 

1시간부터 작업을 완료할때까지 while문을 돌거나 혹은 PQ를 이용해서 작은 시간부터 작업을 완료할때까지 while문을 돌면 시간 초과가 나는 문제이다.

다른 분의 PQ 코드 예시)

 typedef pair<int,int> core;
    priority_queue<core,vector<core>, greater<core>> pq;
    n = n - cores.size(), answer = n;
    while(n> 0 && !pq.empty()) {
        auto t = pq.top();
        pq.pop();
        int time = t.first;
        n-= 1;
        if(n== 0)
            answer = t.second;
        pq.push(core(time + cores[t.second - 1], t.second));
    }

시간을 기준으로 이분탐색을 이용해서 풀어야 되는 문제이다.

현재 시점 전까지 한 작업량과 현재 시점에 한 작업량 수들을 비교 혹은 합해서 n개째의 작업을 한 시간을 구하면 된다.

#include <string>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int solution(int n, vector<int> cores) {
    int answer = 0;
    if(n <= cores.size()) return n;// 코어수 보다 작으면 바로 해당 코어를 반환
    
    int min_v = 999999999;
    for(int i : cores){//가장 작은 처리 시간 구하기
        if(min_v > i) min_v = i;
    }
    //이분탐색을 위해 최소시간과 최대시간 설정
    int start = n / cores.size() * min_v;
    int end = n * min_v;
   
    while(start <= end){
        int mid = (start + end) / 2;
        int cnt = cores.size(); // 0초에 해당 코어들에 작업이 하나씩 들어감
        int current_cnt = 0;// 현재 시간에 할당받은 작업 양
        
        for(int i=0;i<cores.size();i++){
            cnt += mid / cores[i]; // 현재 시간까지 한 양
            if( mid % cores[i] == 0) { //만일 현재 시간에 막 작업을 받은 것이라면
                cnt--;
                current_cnt++;
            }
        }
        if(cnt >= n){ // 현재 시점에 작업받은 것을 추가하지도 않았음에도 n을 넘기면 최대시간 줄임
            end = mid -1;
        }
        else if((cnt + current_cnt) < n) start = mid + 1; // 추가했음에도 n보다 부족하면 최소시간 늘림
        else{ // (현재시점 전에 한 양 + 현재시점에 한 양)이 n을 넘기면
            for(int i = 0; i < cores.size(); i++) {
                if(mid % cores[i] == 0) {
                    cnt++;
                }
                if(cnt == n) { //n개째를 받는 순간의 인덱스를 반환
                    return i+1;
                }
            }
        }
    }
    
    return answer;
}