[프로그래머스,Java] Level3: 선입 선출 스케줄링

 

문제분석

 

목표:  작업들을  순서대로 넣으며 작업하다가  맨 마지막에 작업을 맡게되는 코어를 구하세요.

 

문제를 읽어보면  최적의 시간을 구하는 문제가 아니다.

 

0초에  코어가 비어있다면 무조건 작업을 넣어놓기때문이다.

[1, 1, 100] 의 코어가 있고 4개의 작업이있다면 100의코어에 그냥 집어넣는꼴이다.

 

이를 감안하고 접근을해야한다.

 

 

문제접근 1:  문제설명서대로 풀기

 

 

0초에 모든 작업을 넣고

 

1초에 다시 작업이 가능한지 확인하고

 

2초에 다시 작업이 가능한지 확인하고 

 

. . .

 

마지막 작업이 들어가면 그 코어를 반환하는 로직이다.

 

이렇게 구현하면  매 초마다 모든 코어를 돌려봐야하므로 O(n)만큼 든다.

 

 

-> 정확도는 잘 나오지만  효율성 에러가 뜬다.

 

 

 

문제 접근 2:  효율성 해결

 

아마 효율성 에러가 뜨는 원인은 0초부터  매초 마다  O(n)의 작업을 하기때문일것이다.

 

O(n)의 작업을 최소한 줄이기위해선,   마지막 작업을 수행하는 시간(time)을 구해야한다.

 

 

마지막 작업의 시간을  이분 탐색으로 구한다.

 

최소값은 0  . 최대값은 코어의갯수 * (코어의 최대시간)

 

mid의 시간에  수행한 모든 작업의 갯수가  N보다 작으면 UP  크면 Down을 작업한다. 

 

 

 

이 작업을 시행하면    T*O(N)이   log(T)*O(N)으로 줄어든다.   

 

문제풀이

 

 

import java.util.*;
class Solution {
    public int solution(int n, int[] cores) {
       int answer = 0;
 
        
        int min = 0; // 시간의 최소값
        int max = 10000*n; // 시간의 최대값
 
        int time = 0;
        int m = 0;
 
        while (true) {  
            int mid = (min+max)/2;
 
            int count = calculate(mid, cores);
 
            if(min>max){
 
                break;
            }
            
            if (count >= n) { // 해당시간까지 처리한 작업량보다 n이 크면 time과 m갱신
                max = mid-1;   
                time = mid;     
                m = count; 
            }else{
                min = mid+1;
            }
        }
 
        m-=n; // 처리한 작업량과 n의 차이 갱신
        for(int i = cores.length-1; i>=0; i--){
            if (time % cores[i] == 0) { 
                if (m == 0) {
                    answer = i+1;
                    break;
                }
                m--;
            }
        }
 
        return answer;
    }
    
      static int calculate(int time, int[] cores){
 
        if (time == 0) { // 시간이 0일 때, 처리할 수 있는 작업량은 코어의 개수 
            return cores.length;
        }
 
        int count = cores.length; // 시간이 0일 때, 처리한 작업량 
 
        for(int i = 0; i<cores.length; i++){ // time까지 코어가 처리할 수 있는 작업량 합산
            count += (time/cores[i]);
        }
 
        return count;
    }
}