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

1. 효율성을 고려하지 않은 첫 풀이

function solution(n, cores) {
    const coreLen = cores.length
    // 코어, 준비상태, 준비 잔여시간으로 Object 생성
    const coreDicts = cores.map(core => ({core, isReady: true, remainTime: 0}))
    let result = null
    while(true) {
        // 배열 순회하며 코어 사용가능 여부 확인 및 준비상태 변경
        for(let i = 0; i < coreDicts.length; i++) {
            const curCore = coreDicts[i]
            if(!curCore.isReady) {
                if(curCore.remainTime === 1) curCore.isReady = true
                else {
                    curCore.remainTime--
                    continue    
                }
            }
            n--
            if(n === 0) {
                result = i+1
                return result
            }
            curCore.isReady = false;
            curCore.remainTime = curCore.core
        }
    }
}

정확성은 100점이나, 효율성에서 10점밖에 얻지 못함

2. 효율성을 고려한 O(N log M) 의 시간복잡도 풀이(바이너리 서치)

function solution(n, cores) {
    // 처음에는 모든 코어가 작업하므로, n이 코어의 수보다 작거나 같을 경우 즉시반환
    if (n <= cores.length) return n;
  
    let min = Math.min(...cores);
    // 최악의 경우, 가장 짧은 처리시간을 갖는 코어가 모든 처리를 할 수 있으므로 min*n, Math.max(...cores) 의 경우 잘못된 처리가 됨
    let max = min * n;
    let mid; // 중앙값
    let work; // 각 코어가 처리할 수 있는 작업의 수
  
    // 마지막 작업을 처리하는데 걸리는 시간 계산
    while (min <= max) {
        mid = Math.floor((min + max) / 2);
        // 처음에는 모든 코어가 작업하므로, 작업 수를 코어의 수로 초기화
        work = cores.length;
  
        // 각 코어가 중간 시간 동안 처리할 수 있는 작업의 수를 계산하여 합산
        for (let i = 0; i < cores.length; i++) {
            work += Math.floor(mid / cores[i]);
        }
  
        // 계산한 작업의 수가 n보다 작으면, min을 중간 시간+1로 업데이트
        if (work < n) {
            min = mid + 1;
        } else {
            // 계산한 작업의 수가 n보다 크거나 같으면, max를 중간 시간-1
            max = mid - 1;
        }
    }
  
    // min-1 시점에서 처리한 작업의 수를 계산
    work = cores.length;
    const prevTime = min-1
    for (let i = 0; i < cores.length; i++) {
        work += Math.floor(prevTime / cores[i]);
    }
  
    // min 시점에서 n번째 작업을 처리하는 코어 탐색
    for (let i = 0; i < cores.length; i++) {
        if (min % cores[i] === 0) work++;
        if (work === n) return i + 1;
    }
}