(Leet Code JS)Capacity To Ship Packages Within D Days

https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/description/

Capacity To Ship Packages Within D Days - LeetCode

 

Binary Search 알고리즘.

front와 back을 0으로 선언하고, weights를 한번 순회한다.

front는 현재 front와 w 값 중 max 인 것을 고르고,

back은 weights의 값을 모두 더한 sum을 구한다.

 

이제 while문으로 정답을 유추하면 된다.

front와 back의 중간값인 mid.

mid 값을 적재하는데 걸린 날을 나타내는 countOfDays며, 현재 시작하는 일이 1일차이기 때문에 1로 선언한다.

그리고 weights를 돌면서 적재량을 구할 sum.

 

weights를 map으로 순회한다.

현재 sum값과 w가 mid 이하라면 계속 적재한다.

그렇지 않다면 sum = w로 갱신하고, countOfDays++을 한다.

 

순회가 끝나면 countOfDays <= days인지 검사한다.

만약 days 이하라면 back = mid로 하여 최소값을 구할 수 있을 때까지 반복한다.

days 초과라면 front = mid + 1로 하여 범위를 좁혀 다시 반복한다.

 

만약 front < back을 만족하지 않는다면 front 값이 정답이기 때문에 while문을 탈출하여 리턴하면 된다.

const shipWithinDays = (weights, days) => {
    let front = 0;
    let back = 0;

    weights.map((w) => {
        front = Math.max(front, w);
        back += w;
    })

    while(front < back) {
        let mid = Math.floor((front + back) / 2);
        let countOfDays = 1;
        let sum = 0;
        
        weights.map((w) => {
            if(w + sum <= mid) {
                sum += w;
            } else{
                sum = w;
                countOfDays++;
            }
        })

        if(countOfDays <= days){
            back = mid;
        } else {
            front = mid + 1;
        }
    }
    
    return front;
};