1710. Maximum Units on a Truck

💡 に答える

/**
 * @param {number[][]} boxTypes
 * @param {number} truckSize
 * @return {number}
 */
var maximumUnits = function (boxTypes, truckSize) {
  let result = 0;
  let sum = 0;
  boxTypes.sort((a, b) => b[1] - a[1]);

  for (let [x, y] of boxTypes) {
    sum += x;
    result += x * y;
    if (sum > truckSize) {
      let remain = sum - truckSize;
      result -= remain * y;
      break;
    }
  }
  return result;
};

// 다른 사람의 풀이
var maximumUnits = function (boxTypes, truckSize) {
  boxTypes.sort((a, b) => b[1] - a[1]); // 박스의 per units를 기준으로 큰 순서대로 정렬
  let ans = 0;

  for (let [x, y] of boxTypes) { // 2차원 배열은 이런 방식으로 구조분해 할당을 적용하면 더 깔끔해진다.
    if (!truckSize) break; // truckSize가 없을 경우 반복문 탈출
    let count = Math.min(x, truckSize); // loop을 돌 때마다 truckSize에서 count를 빼주기 때문에 마지막 loop에는 x가 아닌 truckSize가 count에 담기게 된다.
    ans += count * y;
    truckSize -= count;
  }
  return ans;
};

let boxTypes = [
  [5, 10],
  [2, 5],
  [4, 7],
  [3, 9],
];

let truckSize = 10;

maximumUnits(boxTypes, truckSize);

📝 整理する

Greedyは基本タイプの問題です.上は私が初めて解く方法で、下は他の人の私を解く少し変形する方法です.説明は上のコメントと下図で置き換えます.

修正、指摘を歓迎します!

質問リンク

https://leetcode.com/problems/maximum-units-on-a-truck/

LeetCode GitHub

https://github.com/tTab1204/LeetCode