JavaScript로 배열을 합이 같은 세 부분으로 나눌 수 있는지 확인하는 방법

문제 정의

정수 배열을 첫 번째이자 유일한 인자로 받는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열을 세 개의 비어 있지 않은 연속된 부분으로 나눌 수 있고, 각 부분의 합이 서로 같을 경우에만 true를 반환하고, 그렇지 않으면 false를 반환해야 합니다.

예를 들어, 함수에 다음과 같은 배열이 입력되었다고 가정해 보겠습니다.

const arr = [3, 3, 6, 5, -2, 2, 5, 1, -9, 4];

이때 기대하는 출력 결과는 다음과 같습니다.

const output = true;

출력 결과 해설

true가 반환되는 이유는 배열을 아래와 같이 세 부분으로 나눴을 때 각 부분의 합이 모두 6으로 동일하기 때문입니다.

[3, 3] | [6] | [5, -2, 2, 5, 1, -9, 4]
3 + 3 = 6 = 5 - 2 + 2 + 5 + 1 - 9 + 4

풀이 접근 방식

이 문제는 배열 전체의 합을 활용하면 선형 시간 O(n) 안에 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 배열 전체 요소의 합을 구합니다.
2. 전체 합이 3으로 나누어 떨어지지 않으면 세 부분으로 나누는 것 자체가 불가능하므로 즉시 false를 반환합니다.
3. 목표값(target)은 전체 합을 3으로 나눈 값입니다.
4. 배열을 순회하면서 누적합이 목표값에 도달할 때마다 카운트를 1 증가시키고 누적합을 0으로 초기화합니다.
5. 순회가 끝난 후 카운트가 정확히 3이고 마지막 누적합이 0이라면 true, 그렇지 않으면 false를 반환합니다.

구현 코드

위 접근 방식을 코드로 구현하면 다음과 같습니다.

const arr = [3, 3, 6, 5, -2, 2, 5, 1, -9, 4];
const thirdSum = (arr = []) => {
   const sum = arr.reduce((acc, val) => acc + val, 0);
   if(!Number.isInteger(sum / 3)){
      return false;
   };
   let count = 0;
   let curr = 0;
   const target = sum / 3;
   for(const num of arr){
      curr += num;
      if(curr === target){
         curr = 0;
         count += 1;
      };
   };
   return count === 3 && curr === 0;
};
console.log(thirdSum(arr));

실행 결과

위 코드를 콘솔에서 실행하면 다음과 같은 결과가 출력됩니다.

true