프로그래머스 LEVEL 3(선입 선출 스케줄링)

사용 언어 : javascript
해결 날짜 : 2022-12-31
해결 방법 :
- 이분 탐색을 통해 문제 해결
- 처음 시작할 때 모든 코어에 작업이 할당되기에 n에서 cores의 개수만큼 빼줌
  - 단, n이 cores의 개수 이하면 n이 마지막 작업을 처리하는 코어이므로 n 반환
- left는 1, right는 n개의 남은 작업을 X(최대값)의 처리 시간을 가진 코어의 개수로 처리할 수 있는 시간으로 초기화
- 이분 탐색을 수행하며
  - core당 mid 시간내에 수행할 수 있는 최대 용량(capacity)을 합해 구함
  - 최대 용량이 n 이상인 경우, 좌측 탐색
  - n 미만인 경우, 우측 탐색
- 이전 시간대인 right - 1에서 처리한 작업을 제외함으로 n에 right에서 처리할 작업만 남김
- 코어 개수만큼 반복문을 돌리며 현재 시간(right)와 코어의 작업 처리 시간이 나눠 떨어지면
  - 새 작업을 할당하므로 n(작업 수) - 1
  - n이 0이 되는 순간이 마지막 작업을 수행하는 코어
회고 :
- 이분 탐색 후 나온 시간대(right)를 바로 처리하지 않고 그 전 시간대 먼저 처리하는 이유
  - capacity >= rest를 만족하는 조건에서 이분탐색을 수행했기 떄문에 right의 시간은 남은 작업보다 더 많은 작업을 처리한 시간일 수도 있기 때문이다.

코드

function solution(n, cores) {
  if (n <= cores.length) return n;
  n -= cores.length;

  let left = 1,
    right = (Math.max(...cores) * n) / cores.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    let capacity = 0;

    for (const core of cores) {
      capacity += Math.floor(mid / core);
    }

    if (capacity >= n) right = mid;
    else left = mid + 1;
  }

  for (const core of cores) {
    n -= Math.floor((right - 1) / core);
  }

  for (const [index, core] of cores.entries()) {
    if (right % core) continue;
    if (--n === 0) return index + 1;
  }
}

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges