[Programmers] Lv3 선입 선출 알고리즘

Programmers Lv3 선입선출 알고리즘

해당 문제는 언듯 보면 Priority Queue 를 이용하여 시뮬레이션을 하는 문제로 보이지만, 입력조건 n과 cores의 길이를 곱하면 5억 이기 때문에 시간초과를 받게 된다. 입국 심사 문제와 굉장히 유사한 문제로 해당 문제를 풀어보았다면 이 문제가 이분탐색을 이용해야 한다는 것을 눈치 챌 수 있다.

문제 접근

무엇을 이분 탐색의 대상으로 정해야 하는가? 일반적으로 이분 탐색은 구하고자 하는 값과 탐색 범위 값이 일치하는 경우가 많지만 이 문제의 경우 그렇지 않다. 이러한 유형을 Parametric Search 라고 부른다.

이 문제에서는 마지막 작업을 할당받는 core 의 index 를 구하는 것이 목적이고, 검색 범위는 시간을 사용한다.

해결 방법

1. left = 0 right = n * 10000 의 범위에 대해 mid = (left + right) / 2 시간 내에 완료 가능한
   작업의 수를 구한다.
2. 해당 작업의 수가 주어진 작업의 양 n보다 크거나 같다면 작업 수행 시간 time과 작업 수행량 completedTask 를 갱신하고
   right 값을 1 증가 시킨다.
3. 해당 작업의 수가 주어진 작업의 양보다 작다면 left 를  1 감소시킨다.
4. 탐색이 종료되면 completedTask 에서 n을 빼 초과 작업량을 구한다.
5. 문제 조건에 의해 특정 시간에 idle 상태인 코어가 여러개 존재하면 앞선 코어부터 작업이 할당되므로
   역순 탐색을 통해 마지막 작업이 할당된 코어를 찾는다.

Source Code

import java.util.*;

class Solution {
    
    public int calculateTask(int time, int[] cores) {
        int count = cores.length;
        
        if(time == 0) {
            return count;
        }
        
        for(int core : cores) {
            count += (time / core);
        }
        
        return count;
    }
    
    public int solution(int n, int[] cores) {
        int answer = 0;
        int left = 0;
        int right = 0;
        int completedTasks = 0;
        int time = 0;
        
        if(n <= cores.length) {
            return n;
        }
        
        right = 10000 * n;
        
        while(left <= right) {
            int mid = (left + right) / 2;
            int tasks = calculateTask(mid, cores);
            
            if(tasks < n) {
                left = mid + 1;
            } else {
                right = mid - 1;
                time = mid;
                completedTasks = tasks;
            }
        }
        
        completedTasks -= n;
        
        for(int i = cores.length-1 ; i >=0 ; i--) {
            if(time%cores[i] != 0) continue;
                
            if(completedTasks == 0) {
                answer = i + 1;
                break;
            }
            completedTasks--;
        }
        
        return answer;
    }
}