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

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

이분탐색으로 풀 수 있다.
먼저 이분탐색을 통해서 끝나는 시간을 구한다. (finish_time)
이분탐색을 도는 동안 현재 시각에서 core들이 몇개의 일을 했는지 구한 뒤 이들의 합을 구한다.
만약 이 합이 n보다 작으면 left를 mid로 업데이트해주고, 그 반대면 right를 mid로 업데이트 해준다.

이분탐색이 끝나면, finish_time에서 1을 뺀 시간에서 core들의 총 작업 합을 구하고, 이들을 n에서 빼준다.
그 후 finish_time에서 작업을 시작하는 코어들이 있을 때마다 n에서 1씩 빼주고, 만약 0이되면 해당 코어 인덱스를 반환해주면 된다.

사실 이 문제를 풀면서 몇몇 85점인가 90점정도에서 계속 틀려서 좀 헤맸는데, 이분탐색 문제를 풀면서 while-loop 끝나는 조건과 이분탐색 left, right 업데이트에 차이가 있었다.

나는 기존에 while(left <= right) 형태로 while-loop 조건을 걸었고, left = mid + 1; right = mid - 1;로 업데이트를 해줬다.
문제는 이렇게하니 특정 mid 값들이 생략됬고, 그 결과 left~right 사이의 모든 이분탐색이 가능한 mid 값에 대해서 이분탐색이 안된 것 같다.

앞으론 while(left + 1 < right)로 while-loop 조건을 걸고, left = mid; right = mid; 형태로 적는 것이 좋은 것 같다.

코드는 아래와 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int solution(int n, vector<int> cores) {
    int answer = 0;
    int left = 0;
    int right = 1 << 20;
    
    while(left + 1 < right) {
        int mid = (left + right) / 2;
        
        int current = cores.size();
        for(int i=0;i<cores.size();i++) 
            current += (int)(mid / cores[i]);
        
        if(current < n) 
            left = mid;
        else 
            right = mid;
    }
    n -= cores.size();
    if(n <= 0) 
        return n;
    
    for(int i=0;i<cores.size();i++) 
        n -= (int)((right - 1) / cores[i]);
    
    for(int i=0;i<cores.size();i++) {
        if((right % cores[i]) == 0) 
            n--;
        if(n == 0)
            return i + 1; 
    }
    return answer;
}