[LeetCode] 1011.Capacity To Ship Packages Within D Days [JS]

문제

A conveyor belt has packages that must be shipped from one port to another within days days.

The ith package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages on the conveyor belt (in the order given by weights). We may not load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Example 1:

Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
Output: 15
Explanation: A ship capacity of 15 is the minimum to ship all the packages in 5 days like this:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10

Note that the cargo must be shipped in the order given, so using a ship of capacity 14 and splitting the packages into parts like (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) is not allowed.

해결

이진탐색 사용

Packages의 총 무게를 구하고, Packages중에서 가장 무거운 무게를 구하고 변수에 할당한 뒤

각각 이름을 max,reckoning으로 설정했다. (left, right라고 생각하면 된다)

reckoning을 줄여나가면서 범위를 제한시키므로 while문의 조건은 max<reckoning 이 된다.

임의의 수용량을 설정해야 하므로 checkCapacity에 최대값과 전체값을 더해 2로 나눈 값을 설정해준다.(mid)

무게를 더해가면서 수용량을 넘어가면 날짜를 하루 넘기고 수용량을 넘긴 무게부터 다음날에 더해준다.

if ~ else 부분은 else부터 확인하는게 이해하기 쉽다.

필요한 날짜가 기존 날짜보다 적을 경우 전체값(right)에 checkCapacity를 할당해서 값을 줄여준다.

 

ex) 위에 예시에서 reckoning 55, max 10이다 checkCapacity 32 -> 32  10  21 -> 21 10 15 -> 이 다음부터는 if문에 걸림

/**
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function(weights, days) {
  let totalWeight=weights.reduce((pre,cur)=>pre+cur)
  let maxWeight=Math.max(...weights)

  let max=maxWeight
  let reckoning=totalWeight

  while(max<reckoning){
    let checkCapacity=Math.floor((max+reckoning)/2)
    let packedWeights=0,neededDays=1
    for (const w of weights) {
      packedWeights+=w
      if(packedWeights>checkCapacity){
        neededDays++
        packedWeights=w
      }
    }
    if(neededDays>days) max=checkCapacity+1
    else reckoning=checkCapacity
  }
  return reckoning
};
shipWithinDays([1,2,3,4,5,6,7,8,9,10],5)

 

 

 

 

 

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

Capacity To Ship Packages Within D Days - LeetCode