JavaScript로 배열의 중심(피벗) 인덱스 찾기 — 왼쪽 합과 오른쪽 합이 같은 지점 구하기

문제 정의

숫자로 이루어진 배열 arr가 주어졌을 때, 특정 인덱스를 기준으로 왼쪽 요소들의 합과 오른쪽 요소들의 합이 서로 같아지는 지점, 즉 '중심(피벗) 인덱스'를 찾는 JavaScript 함수를 작성해야 합니다.

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

입력

const arr = [1, 7, 3, 6, 5, 6];

출력

const output = 3;

출력 설명

인덱스 3의 값은 nums[3] = 6입니다. 이 인덱스를 기준으로 왼쪽에 있는 숫자들의 합(1 + 7 + 3 = 11)과 오른쪽에 있는 숫자들의 합(5 + 6 = 11)이 정확히 일치합니다.

또한 인덱스 3은 이러한 조건을 만족하는 가장 첫 번째 인덱스입니다.

접근 방식: 누적합 활용하기

이 문제는 매번 왼쪽 합과 오른쪽 합을 새로 계산하면 비효율적입니다(O(n²)). 대신 다음 전략을 사용하면 한 번의 순회(O(n))만으로 해결할 수 있습니다.

1. 배열 전체의 합 sum을 미리 구해 둡니다.
2. 배열을 순회하면서 현재 인덱스까지의 왼쪽 합 currentSum을 누적하고, sum에서는 현재 값을 빼서 '현재 위치 포함 오른쪽 합'을 유지합니다.
3. 두 값이 일치하는 순간의 인덱스를 반환합니다.
4. 끝까지 조건을 만족하는 인덱스가 없다면 -1을 반환합니다.

구현 코드

const arr = [1, 7, 3, 6, 5, 6];

const medianIndex = (arr = []) => {
    let sum = arr.reduce((acc, num) => acc + num, 0);
    let currentSum = 0;

    for (let i = 0; i < arr.length; i++) {
        currentSum += (arr[i - 1] || 0); // 직전 요소까지의 왼쪽 합
        sum -= arr[i];                   // 현재 위치부터의 오른쪽 합

        if (currentSum === sum) {
            return i;
        }
    }
    return -1;
};

console.log(medianIndex(arr));

실행 결과

3

코드 동작 원리 살펴보기

처음 sum은 배열 전체의 합인 28입니다. 반복문이 진행되면서 각 단계는 다음과 같이 변화합니다.

• i = 0: currentSum = 0, sum = 28 − 1 = 27 → 불일치
• i = 1: currentSum = 1, sum = 27 − 7 = 20 → 불일치
• i = 2: currentSum = 8, sum = 20 − 3 = 17 → 불일치
• i = 3: currentSum = 11, sum = 17 − 6 = 11 → 일치! 3 반환

이처럼 왼쪽 합과 오른쪽 합이 처음으로 같아지는 인덱스 3이 결과로 출력됩니다.

복잡도 분석

• 시간 복잡도: O(n) — 배열을 최대 두 번(합 계산 1회 + 순회 1회) 탐색합니다.
• 공간 복잡도: O(1) — 추가적인 배열 없이 변수 몇 개만 사용합니다.

참고로 조건을 만족하는 인덱스가 여러 개일 수 있지만, 문제의 요구사항에 따라 가장 먼저 발견되는 인덱스를 반환하며, 존재하지 않을 경우 -1을 반환하도록 처리했습니다.