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

문제 설명

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

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

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

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

제한사항

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

---

풀이

60분 이상
parametric search풀이법은 빠르게 떠올렸으나, 작업이 모두 들어간 시간을 이용해서 마지막 작업을 처리하는 cpu를 구하는 논리에서 오류가 발생했다. 종료 시간 == 마지막 작업이 들어간 시간이므로, 종료 시간에 진입한 cpu중 가장 나중의 인덱스를 가진 cpu를 찾았다. 하지만

종료시간에 진입하는 작업수 + 이전까지 진입한 작업수 > n 

이면 위의 논리를 적용할 수 없어 문제가 발생한 것 이었다.
어디가 틀린지 몰라서 처음부터(종료 시간을 구하는 코드) 끝까지 하나하나 뜯어보느라 시간이 오래걸린 것이 아쉽다.

실패 코드

// 02 : 37 ~ 
#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> cores) {
    if(n <= cores.size()) return n;
    
    int left = 0, right = n*10000, mid;
    
    int end_time;
    int idx;
    
    while(left < right){
        mid = left + (right - left)/2;
        int cnt = 0;
        for(int core : cores){
            cnt += mid / core + 1;
            if(cnt > n) break;
        }
        
        if(cnt < n) left = mid + 1;
        else right = mid;
    }
    
    end_time = left;
    for(int i =0; i < cores.size(); ++i){
        if(end_time % cores[i] == 0){
            idx = i;
        }
    }
    
    return idx + 1;
}

코드

// 02 : 37 ~ 4 : 00
#include <string>
#include <vector>

using namespace std;

int solution(int n, vector<int> cores) {
    if(n <= cores.size()) return n;
    
    int left = 0, right = n*10000, mid;
    
    int end_time;
    int idx;
    
    while(left < right){
        mid = left + (right - left)/2;
        int cnt = 0;
        for(int core : cores){
            cnt += mid / core + 1;
            if(cnt > n) break;
        }
        
        if(cnt < n) left = mid + 1;
        else right = mid;
    }
    
    end_time = left;
    int cnt = 0;
    for(int i =0; i < cores.size(); ++i){
        cnt += (end_time - 1) / cores[i] + 1;
    }
    
    for(int i =0; i < cores.size(); ++i){
        if(end_time % cores[i] == 0) ++cnt;
        if(cnt == n) return i + 1;
    }
    
    return 0;
}