[LeetCode] Partition Array Into Three Parts With Equal Sum

1.문제

Given an array of integers arr, return true if we can partition the array into three non-empty parts with equal sums.

Formally, we can partition the array if we can find indexes i + 1 < j with (arr[0] + arr[1] + ... + arr[i] == arr[i + 1] + arr[i + 2] + ... + arr[j - 1] == arr[j] + arr[j + 1] + ... + arr[arr.length - 1])

정수 배열 arr가 주어질 때 arr을 3개의 부분으로 나눌 수 있다면 (빈 배열 x) true를 리턴하는 문제이다. 이때 각 부분 배열의 총합은 같아야 한다.

Example 1

Input: arr = [0,2,1,-6,6,-7,9,1,2,0,1]
Output: true
Explanation: 0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1

Example 2

Input: arr = [0,2,1,-6,6,7,9,-1,2,0,1]
Output: false

Example 3

Input: arr = [3,3,6,5,-2,2,5,1,-9,4]
Output: true
Explanation: 3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

Constraints:

• 3 <= arr.length <= 5 * 10^4
• -10^4 <= arr[i] <= 10^4

2.풀이

1. arr의 전체 합을 3으로 나눈 평균값을 구한다.
2. 반복문을 돌면서 부분합이 평균값과 같으면 count 1 올리고 부분합을 0으로 초기화한다.
3. count가 3이상이면 true를 리턴한다.

/**
 * @param {number[]} arr
 * @return {boolean}
 */
const canThreePartsEqualSum = function (arr) {
  // arr 의 총 합
  const sum = arr.reduce((prev, next) => {
    return (prev += next);
  });

  // 3으로 나눈 총 합의 평균
  const average = sum / 3;

  let count = 0;
  let partSum = 0;

  // 반복문을 돌면서 partsum 을 구해서 average 와 같다면 count를 1 올리고 partsum을 초기화한다
  for (let i = 0; i < arr.length; i++) {
    partSum += arr[i];
    if (partSum === average) {
      count++;
      partSum = 0;
    }
  }

  // count 가 3이상이면 true를 리턴
  return count >= 3 ? true : false;
};

3.결과