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