[Java] 선입 선출 스케줄링

 

프로그래머스

 

문제풀이

 

처음 풀었던 풀이는 idx 값과 코어 작업시간을 필드로 갖는 Core 클래스를 만들었다. 그 뒤로 PQ를 사용하여 n 이 0이 될때까지 조건에 맞춰 n을 조작했다. 작업이 처리되는 경우는 현재 코어의 작업처리 시간과 현재시간이 같거나, 현재 코어 작업처리 시간이 현재 시간보다 큰 경우이다. 현재 코어 처리시간이 큰 경우는 현재 시간을 코어 시간으로 처리해준다. 

그 다음 남은 작업이 없다면 반복문을 종료시키고 그때의 코어 인덱스를 반환하게하고 아직 작업이 남았다면 PQ에 새 코어를 만들고 그 코어의 작업처리 시간은 기존 코어 시간에 현재 시간을 더해 다음 처리 시간을 갖도록 한다.

그러나 이 풀이는 시간초과가 났다. 우선 코어의 최대 개수가 10,000개, 코어 당 작업 처리 최대 시간은 10,000, 처리해야 하는 일 최대 개수는 50,000 개이다. 처리해야 하는 일 개수를 1씩 줄이며 코어들을 1개 또는 최악의 경우 1개 이상을 비교해야 하기 때문에 시간초과가 난 것 같다.

 

그래서 이분탐색을 활용하기로 한다. 구해야 하는 값은 마지막으로 작업을 처리하는 코어의 번호이다. 변동되는 값들에 주목해보자. 현재 시간이 몇이냐에 따라서 작업량이 달라진다. 여기서 알 수 있는 사실은 시간의 최소 최댓값을 갖고 이분탐색을 진행하면서 처음으로 n 보다 큰 작업량을 찾았을 때의 시간과 작업량을 구하고 그를 통해 마지막으로 작업되는 코어를 찾는 것이다.

 

마지막 작업 코어를 찾을 때 유의할 것은 우리가 이분탐색을 통해 찾은 값은 최초로 n 보다 큰 작업량을 수행한 시간이라는 것이다. 문제 조건에서 2개 이상의 코어가 남을 경우 앞 코어부터 작업을 처리한다고 되어있다. 이에 따라서 코어 배열의 뒤에서부터 찾아야 n 의 작업중 마지막 작업을 처리한 코어를 찾을 수 있다.

 

핵심 아이디어는 이분탐색이고 우리는 해당 시간에 처리되는 작업량을 구해야 한다. 시간이 0이라면 코어의 개수가 곧 작업량이다. 그리고 현재시간에 코어의 작업시간을 나누면 작업량이 된다. 이를 반환하도록 해주면 된다. 코드는 다음과 같다.

 

 

class Solution {
    public int solution(int n, int[] cores) {
        int answer = 0;
        
        int minTime = 0;
        int maxTime = 10_000 * n / cores.length;
        
        int time = 0;
        int work = 0;
        
        while (true) {
            int midTime = (minTime + maxTime) / 2;
            
            int cnt = calculate(midTime, cores);
            
            if (minTime > maxTime) break;
            
            if (cnt >= n) {
                maxTime = midTime - 1;
                time = midTime;
                work = cnt;
            } else {
                minTime = midTime + 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;
    }
    
    int calculate(int time, int[] cores) {
        if (time == 0) return cores.length;
        
        int cnt = cores.length;
        
        for (int i = 0; i < cores.length; i++) {
            cnt += (time / cores[i]);
        }
        
        return cnt;
    }
}