LeetCode 1011 - Capacity To Ship Packages Within D Days (Medium)

문제

LeetCode - 1011번

풀이 과정

화물들의 무게 weights 가 주어질 때 D 일에 모든 화물을 배송하기 위한 화물선의 최소 무게를 찾는 문제입니다.

사실 문제 분류는 이분 탐색 으로 되어 있지만 입력의 크기를 고려 했을 때 완전 탐색 으로도 해결할 수 있을 것 같았습니다.
그래도 이분 탐색 을 활용해보면 화물선의 최소 및 최대 무게를 정하고
모든 화물을 운반하기 위해 필요한 최소 일수를 구해서 비교하면 됩니다.

회물선의 최소 무게는 모든 화물 중 가장 무거운 것이며
최대 무게는 모든 화물을 하루만에 배송하기 위한 무게(즉, 모든 화물 무게의 합) 입니다.

코드

/**
 * @param {number[]} weights
 * @param {number} D
 * @return {number}
 */
var shipWithinDays = function (weights, D) {
  let lo = Math.max(...weights);
  let hi = weights.reduce((acc, weight) => acc + weight);
  let answer = -1;

  while (lo <= hi) {
    const mid = parseInt((lo + hi) / 2);
    const day = getShippingDay(weights, mid);

    if (day <= D) {
      answer = mid;
      hi = mid - 1;
    } else {
      lo = mid + 1;
    }
  }

  return answer;
};

function getShippingDay(weights, capacity) {
  let day = 1;
  let acc = 0;

  for (const weight of weights) {
    if (acc + weight <= capacity) acc += weight;
    else {
      acc = weight;
      day++;
    }
  }

  return day;
}