[JAVA] 프로그래머스 LEVEL3 선입 선출 스케줄링

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

프로그래머스

코딩테스트 연습 > 연습문제 > 선입 선출 스케줄링

 

난이도: LEVEL3

알고리즘 유형:  이분 탐색(매개 변수 탐색) 

시간 초과 코드

import java.util.*;
class Solution {
    public int solution(int n, int[] cores) {
        int answer = 0;
        // 0: 코어 번호 1: 처리 가능한 시간 2: 처리하는데 걸리는 시간 
        PriorityQueue<int[]> pq = new PriorityQueue<>((o1,o2)->{
            if(o1[1] != o2[1]) return o1[1] - o2[1];
            return o1[0] - o2[0];
        });
        for(int i = 0; i < cores.length; i++){
            pq.add(new int [] {i + 1, 0, cores[i]});
        }
        for(int i = 1; i <= n; i++){
            int [] cur = pq.poll();
            if(i == n ) return cur[0];
            pq.add(new int [] {cur[0], cur[1] + cur[2], cur[2]});
        }
        return answer;
    }
}

 

우선순위 큐를 사용해서 문제를 풀었다. 

우선순위 큐는 처리 가능한 시간이 빠른 순서대로 

만약 처리 가능한 시간이 같다면 코어 번호가 빠른 순서대로 동작하도록 하였다. 

효율성 테스트에서 전부 시간 초과가 발생하였다. 

 

문제는 코어의 개수가 너무 많다는 것이다. 

코어의 개수는 최대 10000개이다.

 50000개의 작업을 10000개의 코어를 우선순위 큐에 넣고 

갱신하는 방식이어서 너무 오래 걸리는 작업이다. 

 

아마 이런 풀이를 생각한 사람도 있을 것이다. 

시간을 1씩 증가시키면서 

작업을 할 수 있다면 카운트 변수를 증가시키면서 카운트 변수가 처리해야 하는 일의 개수와 동일해졌을 때  

해당 작업의 코어 번호를 반환하는 방식

해당 방법은 코어의 개수가 1개 처리해야 하는 일의 개수가 50000 코어가 처리하는 시간이 10000일 때 

50000 * 10000 까지 증가시키면서 탐색해야 한다. 

이 또한 최악의 케이스이며 이와 유사한 테스트 케이스에서 시간 초과가 발생할 것이다. 

문제를 풀고 다른 사람들 풀이를 찾아보니 문제 테스트 케이스가 적을 때 이 방식으로 푼 사람들이 많았다. 

class Solution {
    public int solution(int n, int[] cores) {
        int cnt = 0;
        while(true){
            for(int i = 0; i < cores.length; i++){
                if(cnt % cores[i] == 0 && --n == 0) return i+1;
            }
            cnt++;
        }
    }
}

 

지금 이렇게 풀면 시간 초과가 발생한다. (70점)

 

나는 이분 탐색(매개 변수 탐색)을 활용했다. 

이분 탐색으로 먼저 최소 시간을 찾는다.

 

최소 시간이란?

문제에서 원하는 작업량(n)을 넘어서는 시간이다. 

int start = 0;
int end   = 500000001; 
while(start < end){
    int mid = (start + end) / 2;
    long result = function(mid, cores);
    if(result >= n){
        end = mid;
    }
    else start = mid + 1;
}

public static long function(int time, int [] core){
    long sum = size;
    for(int next : core){
        sum += time / next;
    }
    return sum;
}

최소 시간을 구했다면

해당 시간을 사용했던 매개변수 탐색 함수에 인자로 넘겨서 해당 시간에 처리 가능한 작업량을 받는다.

 

이제 시간을 1씩 증가시키면서 탐색했던 방식과 비슷하게

코어 뒤에서부터 해당 시간에 코어가 처리하면 받은 작업량을 줄이면서  작업량이 같으면 

멈추고 해당 코어 번호를 반환하고 코어를 다 돌았는데 작업량이 원하는 작업량(n)보다 크면

시간을 1 줄이고 다시 코어를 뒤에서부터 처음까지 탐색한다. 

해당 방식을 반복한다. 

long job = function(end, cores); 
int time = end;

while(true){
    for(int i = size - 1; i >= 0; i--){
        if(time % cores[i] == 0){
            job--;
            if(job == n - 1){
                return i + 1;
            }
        }
    } 
    time--;
}

 

내가 실수한 부분 

여기서 내가 실수한 부분은 function의 반환값을 int로 했었다. 

int 타입으로 계산하면 특정 케이스에서 int 범위를 넘어서 - 가 되는 케이스가 있을 것이다. 

3개 케이스에서 틀림 

 

ex)

function 메소드 매개변수인 time이 250000000 코어의 개수가 10000개 각 걸리는 시간이 모두 1이면 

250000000 * 10000의 작업량이 처리 가능한데 해당 숫자는 int를 넘어간다.

타입을 long으로 하자 

정답 코드

class Solution {
    static int size;
    public int solution(int n, int[] cores) {
        size = cores.length;
        int start = 0;
        // 처리하는 시간(10000) * 일의 개수(50000) / 코어 개수(1)
        int end   = 500000001; 
        while(start < end){
            int mid = (start + end) / 2;
            long result = function(mid, cores);
            if(result >= n){
                end = mid;
            }
            else start = mid + 1;
        }
        long job = function(end, cores); 
        int time = end;
        while(true){
            for(int i = size - 1; i >= 0; i--){
                if(time % cores[i] == 0){
                    job--;
                    if(job == n - 1){
                        return i + 1;
                    }
                }
            } 
            time--;
        }
    }
    public static long function(int time, int [] core){
        long sum = size;
        for(int next : core){
            sum += time / next;
        }
        return sum;
    }
}