[javascript] 프로그래머스 level 3 - 선입 선출 스케줄링 feat.parametric search

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

프로그래머스

문제 설명

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.

이 CPU는 다음과 같은 특징이 있습니다.

• CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
• 한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
• 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.

처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.

제한 사항

• 코어의 수는 10,000 이하 2이상 입니다.
• 코어당 작업을 처리하는 시간은 10,000이하 입니다.
• 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.

---

문제 풀면서 어려웠던 점

- 효율성 고려하기가 어려움 (처음엔 시간 1지날때마다 스케줄러가 끝났는지 아닌지 확인해서 끝나면 작업 추가해주는 방식으로 풀었다가 효율성 테스트에서 1문제 맞음)

- 사실상 처음에 이분 탐색으로 찾아야 효율성 고려할 수 있다는 것은 알았지만 .. 이분 탐색으로 찾은 값이 정확히 뭘 구해주는 건지 몰라서 풀지 못했음

 

문제 해결 방법

1. 먼저 core개수가 n보다 크다면 n을 리턴한다.(처음에는 모두 할당 가능하기 때문에)

2. min = Math.min(...cores) (이미 core가 n보다 많은 경우는 배제했기 때문에 최솟값은 cores에서 시간이 가장 짧게 걸리는 게 최솟값임)

3. max = min * n (짧게 걸리는 스케줄러가 모든 프로세스를 처리할 때가 최대)

4. min < max 조건으로 while문

5. mid = Math.floor((min + max)/2) 시간이 mid일때 총 처리량이 얼만지 구한다.

6. 시간이 h일 때 총 처리량 = core개수(처음에 모두 할당하니깐) + Math.floor(h/cores[i])

(이 것의 포인트는 h일때 몇개의 프로세스를 완료시켰냐가 아니라 현재 몇개의 프로세스가 돌아가고 있느냐이다. 만약 h일때 몇개가 완료됐냐고 하면 core개수를 더하지 말아야 함)

7. min시간일 때 총 처리량은 원하는 n과 같거나 n보다 크게 됨

(즉, min - 1시간일 때 총 처리량이 n보다 작은 것 중 가장 큰 값 => min-1일 때 총 처리량 < n <= min일때 총 처리량 )

9. min - 1 일때 총 처리량(total)을 구하고, cores에서 min % cores[i] === 0 이라면 처리량(total) 증가 시킴

10. total이 n과 같아지면 i + 1 을 리턴함 (0번 인덱스 코어 -> 1번째 코어)

---

코드

function solution(n, cores) {
    const coresNum = cores.length
    if(coresNum > n) return n
    let min = Math.min(...cores)
    let max = min * n
    let mid;
    let total;
    
    while(min < max) {
        mid = Math.floor((min + max)/2)
        total = cores.reduce((a,c) => a+Math.floor(mid/c), coresNum)
        if(total >= n) {
            max = mid
        } else {
            min = mid + 1
        }
    }
    
    total = cores.reduce((a,c) => a + Math.floor((min-1)/c), coresNum)
    
    for(let i =0; i < coresNum; i++) {
        if(min%cores[i] === 0) total++
        if(total === n) return i + 1
    }
    
}

---

배운점

- 최종으로 구한 min에서의 값이 원하는 값과 같거나 크다는 것을 알게됨

-> min에서의 값이 원하는 값보다 작은 것 중 가장 큰 값인지, 아니면 원하는 값보다 무조건 큰 값인지, 아니면 원하는 값이랑 같거나 큰건지 몰랐지만 직접 .. 표에 그려가며 해본 결과 이때 나오는 min에서의 값은 우리가 원하는 값과 같거나 그것보다 크다는 것을 알게 되었다.

-> 참고

원하는 값은 n=6 일때 최종 min값은 2임.

만약 2의 값이 7이라고 가정하자.

이때도 n=6 일때 최종 min값은 2이므로, min일때 값이 목표값과 같거나 크다는 것을 알 수 있다.

-> while 조건 min<max, arr[mid] >= n 일때 max = mid, arr[mid] < n 일때 min = mid + 1 인 상황에서 최종 arr[min]은 n보다 같거나 크다!