[자바] 선입 선출 스케줄링

문제

풀이

이 문제는 푸는데 정말 고생이 많았다...

문제에서 필요로 하는 답은 "마지막 작업을 받은 코어" 의 번호를 찾는 것인데

정작 내가 구하려 한 답은 "마지막으로 작업을 마친 코어" 라 아무리 답을 구해도 제출만 하면 틀리게 나와서 상당히 고생했다.

사실 그런 제외하고도 고려할게 많은 문제긴 하다.

가장 먼저 내가 접근한 방법은 Core 객체를 만들고 그 객체들을 저장해둔 배열에 반복문을 통해 순차적으로 작업을 넣어주는 것이었다.

이 방법으로 진행했을 때, 깔끔하게 문제는 해결되었는데 효율성이 시간 초과가 나왔다. 아무래도 반복문을 사용하다보니 O(n)의 시간 복잡도를 사용하게 되어 문제가 발생한 것으로 예상되었다.

시간을 줄이기 위해 내가 선택한 방법은 이분탐색 알고리즘을 통해 마지막 입력 직전의 시간을 찾고, 그 시간대에 무엇이 입력되는지 탐색하는 방법이다.

import java.util.*;

class Solution {
    public int solution(int n, int[] cores) {
        
        Core[] CoreArr = new Core[cores.length];
        
        for(int i=0; i<cores.length; i++){
            CoreArr[i] = new Core(cores[i]);
        }

        int max = cores[0]*n;                               //코어에 입력이 끝나는 시점(최대)
        int min = (int)Math.ceil((double)n/cores.length);   //코어에 입력이 끝나는 시점(최소)
        
        //코어에 입력이 끝나는 시점을 찾는 이분탐색법
        while(min<=max){
            int mid = (max + min)/2;
            //완수한 작업량
            int leftJob = leftJob(n,mid,cores);
            
            if(leftJob<=0){             //남은 작업이 없을 경우
                max = mid - 1;   
            }else{                      //남은 작업이 있을 경우
                min = mid + 1;
            }
        }
        
        //left 마지막 입력 직전 남은 작업량
        int left = leftJob(n,max,cores);
        int ansIdx = -1;
        
        //마지막 입력 기준으로 모든 코어의 남은 시간을 체크
        for(int i=0; i<cores.length; i++){
            //coreLeft = 이 코어의 남은 시간
            int coreLeft = CoreArr[i].checkCore(max+1);
            if(coreLeft < 1 && left > 0){   //코어가 작업중이 아니고 남은 작업이 있다면
                left--;
                ansIdx = i+1;
            }
            if(left < 1) break;
        }

    
        return ansIdx;

    }
    
    //입력된 시간에 아직 작업중이 아닌 작업량을 return
    public static int leftJob(int n,int time, int[] cores){
        int cnt = 0;
        for(int i=0; i<cores.length; i++){
            cnt += time/cores[i] + 1;
        }
        return n-cnt;
    }
    
    //코어 객체 생성
    public class Core{
        private int speed;
        private int leftTime = 0;
        
        public Core(int p){
            this.speed = p;
        }
           
        //작업량이 무한이라고 가정하고 해당 시간 기준으로 남은 작업시간을 구함
        public int checkCore(int time){
            long tmp = this.speed * (int)Math.ceil((double)time/this.speed);
            if(time>this.speed){
                return (int)(tmp - time);
            }else{
                return this.speed - time;
            }
        }
        
    }
}

처음에 Core 객체를 만들어주고 while문을 통해 이분탐색 알고리즘으로 남은 작업량이 가장 적은 시간대를 구했다.

그리고 그 시간을 기준으로 남은 작업량과 새로 작업에 들어갈 수 있는 코어를 찾아 순서대로 넣어주고 마지막 작업을 받은 Core의 인덱스를 기록해 두었다가 남은 작업량이 0이 되는 순간 결과값을 return해주면 정답이 나온다.