[리트코드] 1011 - javascript

📌 문제

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

📌 풀이

/**
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function (arr, k) {
  let sum = arr.reduce((a, b) => a + b);
  let left = 1;
  let right = sum;
  let ans = Infinity;
  while (left <= right) {
    let mid = parseInt((left + right) / 2);
    let cnt = 1;
    let cur = 0;
    for (let i = 0; i < arr.length; i++) {
      if (arr[i] > mid) {
        cnt = Infinity;
        break;
      }
      if (cur + arr[i] <= mid) {
        cur += arr[i];
      } else {
        cnt++;
        cur = arr[i];
      }
    }
    if (cnt <= k) {
      if (mid < ans) {
        ans = mid;
      }
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  return ans;
};

✔ 알고리즘 : 이분탐색

✔ arr에는 각 박스의 무게가 들어가있는 배열이다. 컨베이어 벨트의 모든 포장이 k일 이내에 발송될 수 있도록 선박의 최소 중량 용량을 반환해야 하는 문제이다.

✔ 전형적인 이분탐색 문제로 left를 1 right를 무게의 합으로 설정하고 시작하였다.

✔ left와 right의 중앙을 mid로 설정하고 arr[0]부터 탐색을 시작한다.

✔ mid가 될때까지 계속 합을 더하다가 넘으면 cnt를 1증가 시키고 cur을 현재 index의 weight으로 갱신한다.

✔ 모든 탐색이 끝났을 때 cnt를 k와 비교하여 k보다 작거나 같은경우 ans와 비교하여 작으면 ans을 갱신한다.

✔ cnt가 k보다 작거나 같으면 right을 줄여주고 cnt가 k보다 크면 left를 증가시킨다.

❗ arr[i]가 mid보다 큰 경우 현재의 mid로 포장할 수 없는 경우이므로 cnt를 Infinity로 변경시키고 break 해줘야 한다.

✔ 난이도 : 리트코드 기준 medium