[lv3] 선입 선출 스케줄링

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

 

이분탐색 문제다.

1. 이분탐색 이후 "마지막으로 작업을 처리한 코어"를 도출하는 방식을 찾기가 어려웠다.

2. time % cores[i] == 0이 현재 작업 가능한 코어를 의미함을 찾기가 어려웠다.

 

풀이

 

1. [min : n을 모두 처리하는데 걸리는 최소 시간]을 이분 탐색으로 구한다.

2. (min -1)초를 재현하여 남은 작업량을 구한다.

3. min에 현재 작업 가능한(작업을 처리 중이지 않은) core를 순차 탐색하며 n = 0이되는 코어를 찾는다.

 

복기

 

"마지막으로 작업을 처리한 코어"를 도출하는 다른 방법

1. [min : n을 모두 처리하는데 걸리는 최소 시간]을 이분 탐색으로 구한다.

2. [work : min에 처리 가능한 작업량]를 구한 후, work -= n하여 n만큼 처리하고 남는 작업량을 구한다.

3. cores.length-1 to 0으로 역방향 탐색하며, work  = 0이되는 코어를 찾는다.

(work가 0이라는 것은, 문제에서 필요한 처리량인 n만큼 처리한 마지막 코어임을 의미한다.)

for(int i=cores.length-1; i>=0; i--){
    if(min%cores[i]==0){
        if(n==0){
            answer = i+1;
            break;
        }
        n--;
    }
}

 

 

class Solution {
    public int solution(int n, int[] cores) {
       int answer = 0;

       /*
        * 코어의 수는 10,000 이하 2이상 입니다.
        * 코어당 작업을 처리하는 시간은 10,000이하 입니다.
        * 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.
        */
       int high = 50000 / 2 * 10000;
       int low = 0;
       int min = high;

       // n에서 0초에 할당되는 작업량을 제외
       n = n - cores.length;

       if(n < 1)
          return 0;

       while(low <= high) {
          int mid = (low + high) >>> 1;
          int midVal = n;

          for(int i=0; i<cores.length; i++) {
             midVal -= mid / cores[i];

             if(midVal < 1) break;
          }

          // 작업을 다 처리한 경우
          if(midVal < 1) {

             // 걸린 시간이 기존보다 작다면
             if(mid < min) {
                min = mid;
             }
             high = mid - 1;
          }
          else {
             low = mid + 1;
          }
       }

       // min : 작업 완료에 걸리는 최소 시간
       // work : (min - 1) 까지 수행하고 남은 작업량
       int work = n;
       for(int core : cores)
          work -= (min - 1) / core;

       // min에 작업을 완료 했을 때, 마지막 처리 코어 도출
       for(int i=0; i<cores.length; i++) {
          // 코어가 작업이 처리 가능한 상태면,
          if(min % cores[i] == 0) {
             work--;
             if(work < 1) {
                answer = i + 1;
                break;
             }
          }
       }

       return answer;
    }
}