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

문제 설명

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

문제 풀이

• 이분탐색으로 풀이하였다.
• 시간을 기준으로 이분탐색으로 줄이고 늘려가며 마지막 작업이 진행되는 시간을 찾고 시간을 찾으면 마지막 작업을 수행하는 코어 번호를 계산한다.
• 코어 번호 계산은 해당 시간에 완료된 작업수, 해당 시간에 착수한 작업수를 기준으로 계산 가능하다.
• 이분 탐색에 쓰이는 최대 시간은 n * 최대 코어 시간 / 코어 갯수로 계산하였고
  문제의 조건에 의해 시간 복잡도는 O(코어갯수 * log(시간 범위))이다.

소스 코드 (JAVA)

import java.util.*;

class Solution {
    public int N;
    public int[] C;
    public int INF = 987654321;

    // INF : t 늘려야함
    // 0 : 해당 시간이 맞음
    // -INF : t 줄여야함
    public int check(int t) {
        //나머지가 0인 코어 번호 리스트
        List<Integer> zeroList = new ArrayList<>();

        //해당 시간에 들어가 있는 작업 갯수
        int insertCnt = 0;

        for (int i = 0; i < C.length; i++) {
            insertCnt += (t / C[i] + 1);
            if (t % C[i] == 0)
                zeroList.add(i + 1);
        }

        if (insertCnt < N) return INF;
        else if (N <= insertCnt - zeroList.size()) return -INF;
        //마지막 작업 코어 번호 리턴
        else {
            return zeroList.get(N - (insertCnt - zeroList.size()) - 1);
        }
    }

    public int solution(int n, int[] cores) {
        //초기화
        N = n;
        C = cores;
        int maxT = 0;
        for (int i = 0; i < C.length; i++)
            maxT = Math.max(maxT, C[i]);

        //이분 탐색 진행
        int hi = N * maxT / C.length + 1;
        int lo = 0;

        while(lo < hi) {
            int mid = (lo + hi) / 2;
            int res = check(mid);

            if (res == INF) lo = mid;
            else if (res == -INF) hi = mid;
            else return res;
        }
        return 0;
    }
}