1769. Minimum Number of Operations to Move All Balls to Each Box

💡풀이

// Brute force << 내 풀이
var minOperations = function (boxes) {
  let answer = [];
  for (let i = 0; i < boxes.length; i++) {
    let sum = 0;
    for (let j = 0; j < boxes.length; j++) {
      if (boxes[j] === '1') {
        sum += Math.abs(i - j);
      }
    }
    answer.push(sum);
  }
  return answer;
};

// DP << 공유 받은 풀이
var minOperations = function (boxes) {
  const len = boxes.length;
  const leftToRightDp = new Array(len);
  const rightToLeftDp = new Array(len);

  (leftToRightDp[0] = 0), (rightToLeftDp[len - 1] = 0);

  let oneCount = boxes[0] === '1' ? 1 : 0;

  for (let i = 1; i < len; i++) {
    leftToRightDp[i] = leftToRightDp[i - 1] + oneCount;

    if (boxes[i] === '1') {
      oneCount++;
    }
  }

  oneCount = boxes[len - 1] === '1' ? 1 : 0;

  for (let i = len - 2; i >= 0; i--) {
    rightToLeftDp[i] = rightToLeftDp[i + 1] + oneCount;

    if (boxes[i] === '1') {
      oneCount++;
    }
  }

  const ret = [];

  for (let i = 0; i < len; i++) {
    ret.push(leftToRightDp[i] + rightToLeftDp[i]);
  }

  return ret;
};

console.log(minOperations('001011'));

📝정리

내 풀이는 모든 부분을 탐색하면서 boxes[j] === '1'일 때 마다 sum을 더해주는 식이었다. 뭔가 다른 방법이 있을 것 같아서 생각을 해봤지만 다른 방법을 생각하지 못했던 문제였다. (내가 사용한 방법은 절반 정도의 성능 - 생각하기 쉬운 방법)

이후 리뷰 때 DP를 이용한 방법을 공유 받았는데, 풀이 설명을 듣고 간신히 이해했는데 코드도 이해하는데 시간이 매우 오래 걸렸다. 코드는 이해했지만 이 방법으로 스스로 풀어보라고 하면 아직은? 못 풀 그런 문제다.

수정, 지적을 환영합니다!

문제 링크

https://leetcode.com/problems/minimum-number-of-operations-to-move-all-balls-to-each-box/

LeetCode GitHub

https://github.com/tTab1204/LeetCode