[프로그래머스] 선입선출 스케줄링 java 문제 풀이

1. 문제 설명

문제 링크

처리해야할 작업의 양: n
코어의 개수와 코어마다 일을 처리하는데 걸리는 시간 : int [] cores
맨 마지막에 일을 끝내는 코어의 번호를 구하라. (번호는 1부터 시작한다.)

2. 접근 방식

KEY WORD: binary_search

1. 이분탐색으로 n의 작업량 이상의 처리를 하는 시간대 중 가장 작은 시간대(k)를 구한다.
   (n = 15라고 하자. 시간별로 짤랐을 때, 16이 가장 가까운 수 이다.)
2. 코어의 맨 마지막 자리부터 k 시간대 일을 하는 녀석을 하나하나 제외시켜가면서 맨 마지막으로 n번째 일을 처리한 코어를 구하고 번호를 출력한다.
   9시간째에서는 1번 코어와 2번코어만 일하며 16번째인 2번 코어를 제외하면 1번코어가 target값인 15를 처리하는 마지막 코어이다. 그래서 답은 1이다.

(1) 사전 지식

처리에 걸리는 시간 단위를 hour(이하 H)라고 두자.
0H 즉 작업을 시작하는 시점에서는 모든 코어가 비어있음으로, 모든 코어가 일을 시작한다.
NH일 때 처리하는 작업의 개수가 몇 개인지 셀 수 있는가? (처리하는 작업: 현재 처리 중인 거랑, 처리 끝난 것을 합친 것)

만약 cores = {1,3,5} 이고 10H일 때 일을 몇 개 끝냈는지 확인해보자.
먼저 0H에 모두 작업을 진행했음으로, 기본적으로 3개의 일은 처리했다.
이후 각 코어는 자신의 일 처리 시간의 배수마다 일을 더 한다. 따라서 첫 번째 코어는 10H에서 10개의 일을 끝냈고, 3은 3개의 일을, 5는 2개의 일을 끝냈을 것이다. 따라서 10H에 진행된 일은 18개 이다. 그림으로 설명하겠다.

그렇다 우리는 시간이 주어지면, 그때까지 처리한 일을 구할 수 있다. 이를 이용해 이분탐색을 한다.
그럼 이분 탐색은 무엇을 기준으로 하고, target은 무엇이며 어떻게 움직여야 할까?

(2) 이분 탐색의 사용

우리는 경과된 시간을 통해 누적된 처리량을 구할 수 있었음으로, 시간을 기준으로 이분탐색을 한다. 다음과 같이 진행된다.

1. 이분탐색에는 천장(top)과 밑바닥(bottom)이 존재한다. 여기서 top은 제일 오래 걸리는 코어가 모든 일을 처리했을 경우로 가정한다. bottom은 1로 두겠다.
2. mid 값은 당연하게도 이 둘의 절반이다.

이분탐색의 다음 범위 결정 기준은? 🤔

mid값은 경과된 시간을 뜻하므로, 해당 mid 시간에 누적된 처리량(work)을 구한다.
구하는 법은 (mid/cores의 각 원소)들의 합 + 초기 처리량(cores.length) 이다.
이렇게 나온 누적된 처리량과 우리가 목표로 하는 처리량(n)을 비교한다.

1. n > work 이면, bottom = mid+1 하여 상향한다.
2. n < work이면, top = mid-1 하여 하향한다.
3. n == work 이면 top = mid-1 하여 하향한다.

3번 경우는 왜 그런지 파고들기 🔎

왜 n == work로 딱 맞았는데, top = mid-1로 하향할까? 이유는 다음과 같다.
우리는 LowerBound를 활용 해야한다. (해당 개념을 모르는 분들은 이분 탐색 & Upper Bound, Lower Bound 개념 정리보고 오기)
UpperBound를 쓰면 다음과 같은 문제가 있다. n과 경과시간별 처리량이 같은 경우, 즉 예시에서 2H에서 처리량은 n과 같은 6인데, upperBound로 하면, mid == 2 일 때의 처리량과 n이 같으면 상향하므로, 8을 return한다.
당초 우리 계획은 목표값이 들어있는 경과 시간을 구해서, 맨 오른쪽의 코어부터 확인 후 제외해가며, 맨 마지막으로 계산된 코어를 구한다 였다. 하지만 UpperBound로 값을 구하면 애초에 목표로 하는 처리 개수가 들어있는 경과시간을 선택하지 못해서 답을 구하지 못한다.
다음은 내 설명을 그림으로 표현한 것이다.

uppperBound에 누적 처리량 8인 3시간째를 구해버리면, 그 안에서 아무리 loop를 돌아도 6번째 처리 Core를 찾지 못한다.

3. 코드 분석

import java.io.*;
import java.util.*;
// 0. core별로 작업 처리 시간이 적혀 있어서, N초에 얼마나 일을 끝냈는지 확인 가능 
// 1. 일의 개수를 기준으로 이분 탐색 + upper bound로 초과해서 일을 한 것 중 target에 가까운 최소값 찾기 
// 2. 최소값에서 코어 하나씩 지워가며, 마지막으로 일한 코어 찾기

class Solution {
    public int solution(int n, int[] cores) {
        int ceilingTime = bs_time(n, cores);
        int work = cores.length;
        for(int i = 0; i < cores.length; i++){
            work += ceilingTime/cores[i];
        }
        int t = cores.length-1; 
        while (work >= n){
            if(ceilingTime%cores[t] == 0) {
                t--; work--;
            }else{
                t--;
            }
        }
        return t+1+1;
    }
    // tgt에 제일 가까우면서도 그것을 초과하는 일의 개수를 처리하는 `시간`을 구한다.     
    public int bs_time(int tgt, int [] cores){
        int top = 10000 * tgt; // 천장: 제일 오래 걸리는 코어로만 일처리 했을 때 걸리는 시간
        int btm = 1; 

        while(btm <= top) {
            int mid = (top + btm)/2;
            int amt = cores.length; // mid 시간에 처리할 수 있는 일의 량
            for(int i = 0; i < cores.length; i++){
                amt += mid/cores[i];
            }
            if(amt < tgt) btm = mid+1;
            else if(amt >= tgt) top = mid-1;
        }
        return btm;
    }
}

4. 접근 방식을 떠올리지 못 했던 이유가 뭘까?

1. 문제를 너무 풀지 않아서 감이 떨어졌다.
2. 이분탐색의 기준을 설정하지 못했다. (무엇을 기준으로 bottom, top, mid를 구할지, 무엇으로 mid와 target을 비교할지)
   또한 해당문제는 처리시간을 구해서 그 처리시간에 따른 처리량을 비교해야 해서 덜 직관적이였다. 이 또한 한 몫한 듯.