JavaScript 배열에서 요소 하나를 제거해 홀수·짝수 인덱스 합을 같게 만드는 모든 경우의 수 구하기

숫자 배열을 첫 번째이자 유일한 인수로 받는 JavaScript 함수를 작성해야 합니다.

이 함수는 배열에서 요소를 하나 제거했을 때, 홀수 인덱스에 위치한 요소들의 합과 짝수 인덱스에 위치한 요소들의 합이 같아지는 경우를 찾아야 합니다. 그리고 조건을 만족시키기 위해 한 번에 하나씩 요소를 제거할 수 있는 서로 다른 모든 방법의 개수를 세어 반환해야 합니다.

문제 이해하기

예를 들어 입력 배열이 다음과 같다고 가정해 보겠습니다.

const arr = [2, 6, 4, 2];

이때 출력값은 2가 되어야 합니다. 인덱스 1에 있는 6과 인덱스 3에 있는 2, 이 두 요소를 각각 제거했을 때 조건이 충족되기 때문입니다.

요소 6을 제거하는 경우

[2, 4, 2] → 홀수 인덱스의 합 = 짝수 인덱스의 합 = 4

마지막 요소 2를 제거하는 경우

[2, 6, 4] → 홀수 인덱스의 합 = 짝수 인덱스의 합 = 6

나머지 두 요소(인덱스 0의 2, 인덱스 2의 4)를 제거할 때는 두 합이 같아지지 않으므로, 최종 결과는 2가 됩니다.

접근 방법

매번 요소를 실제로 제거하고 배열 전체를 다시 순회하면 시간 복잡도가 O(n²)까지 증가할 수 있습니다. 대신 누적합(prefix sum)을 활용하면 O(n) 시간 안에 문제를 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다.

먼저 각 인덱스까지의 짝수 인덱스 누적합과 홀수 인덱스 누적합을 미리 계산해 둡니다.
특정 인덱스의 요소를 제거하면, 그 뒤에 있는 요소들은 인덱스 성격이 뒤바뀌므로(짝수 ↔ 홀수), 누적합을 이용해 제거 후의 좌측 합과 우측 합을 상수 시간에 구할 수 있습니다.

예제 코드

다음은 위 접근 방식을 구현한 코드입니다.

const arr = [2, 6, 4, 2];
const possibleWays = (arr = []) => {
    const sum = new Array(arr.length);
    let res = 0;
    let oddSum = 0;
    let evenSum = 0;
    for (let i = 0; i < arr.length; ++i) {
        if (i % 2 === 0) sum[i] = (evenSum += arr[i]);
        else sum[i] = (oddSum += arr[i]);
    }
    for (let i = 0; i < arr.length; ++i) {
        if (i % 2 === 0) {
            if (2 * sum[i] - arr[i] + oddSum === 2 * (sum[i - 1] || 0) + evenSum) ++res;
        } else if (2 * sum[i] - arr[i] + evenSum === 2 * (sum[i - 1] || 0) + oddSum) {
            ++res;
        }
    }
    return res;
};
console.log(possibleWays(arr));

출력 결과

콘솔 출력은 다음과 같습니다.

이처럼 누적합을 사전에 계산해 두면, 각 요소를 제거하는 모든 경우를 단 한 번의 추가 순회만으로 검증할 수 있어 매우 효율적인 풀이가 가능합니다.