[pro] 프로그래머스 level3 12920 선입 선출 스케줄링 (Java) - 이분탐색

[문제]

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

프로그래머스

 

[풀이]

for문 반복으로 초를 증가시켜가며 n의 개수를 감소시키거나 우선순위 큐를 이용하는 방법도 있지만 시간초과가 발생하므로 효율적으로 풀기위한 방법을 찾아야 하는 문제.

 

이분탐색으로 풀 수 있다. 이분탐색을 하기 위해서는 이분탐색의 기준이 되는 값을 무엇으로 정할 지가 중요하다.

 

	cores[0]=1	cores[1]=2	cores[2]=3	누적값
0H	o	o	o	3개
1H	o	x	x	4개
2H	o	o	x	6개
3H	o	x	o	8개
4H	o	o	x	10개

 

예제1을 표로 표현하면 다음과 같다. 0H에 모든 cores에 작업이 들어가고, 각 core가 작업을 처리하는 시간의 배수마다 작업이 들어갈 수 있다. 즉, 수행 시간에 대해서 총 몇 개의 작업이 수행 가능한 지 알 수 있다.

따라서 이분탐색의 기준을 수행 시간으로 정하고, high 값을 코어의 최대 처리 시간*n으로 했다.

기준 시간 동안 처리 가능한 작업의 양을 구한 후, 그 값이 n이랑 같거나 n보다 크다면 더 적은 시간 내에 수행 가능한지 알기 위해 high를 mid-1로, 그렇지 않다면 low를 mid+1로 한다.

 

반복문이 끝나면 n개 이상의 일을 수행할 수 있는 최소 시간 time을 구할 수 있다.

이제 이때의 작업량 work에 대해서 n번째 일을 수행하는 core의 번호를 구해야 한다. n개보다 더 초과한 작업량 work -= n에 대해서 core를 돌며 수행 가능하다면 work를 감소해주며 정답 index를 찾을 수 있다. 이때, 앞의 코어부터 작업을 처리하므로 마지막 코어를 알기 위해서는 index를 감소시는 방향으로 반복문을 돌아야 한다.

 

[코드]

 

import java.util.*;

class Solution {
    public int solution(int n, int[] cores) {
        int answer = 0;
        
        int len = cores.length;
        
        if(n<=len) return n;
    
        //작업 시간
        int low = 1;
        int high = 10000*n;
        int time = 0;
        int work = 0; //작업량
        
        //n개의 일을 수행 가능한 최소 시간 time을 구함
        while(low<=high){
            int mid = (low+high)/2;
            
            //작업 처리 시간 동안 처리 가능한 일의 양
            int count = cal(mid, cores);
            
            if(count>=n){
                high = mid-1;
                time = mid;
                work = count;
            }
            else{
                low = mid+1;
            }
        }
        
        work -= n;
        for(int i=cores.length-1; i>=0; i--){
            if(time%cores[i]==0){
                if(work==0){
                    answer = i+1;
                    break;
                }
                work--;
            }
        }
        
        return answer;
    }
    
    public int cal(int mid, int[] cores){
        //0초에 모두 코어에 진입함
        int count = cores.length;
        
        for(int i=0; i<cores.length; i++){
            count += mid/cores[i];
        }
        
        return count;
    }
}