C++ 배열의 평형 인덱스(Equilibrium Index) 찾는 방법

이 문제에서는 n개의 정수로 이루어진 배열 arr[]가 주어지며, 우리의 목표는 배열의 평형 인덱스(Equilibrium Index)를 찾는 프로그램을 작성하는 것입니다.

평형 인덱스란?

평형 인덱스란 해당 인덱스를 기준으로 왼쪽(앞쪽)에 있는 모든 요소의 합과 오른쪽(뒤쪽)에 있는 모든 요소의 합이 서로 같아지는 지점을 의미합니다.

크기가 n인 배열 arr[]에서 평형 인덱스 e는 다음 조건을 만족합니다.

sum(arr[0 … e-1]) = sum(arr[e+1 … n-1])

예제로 문제 이해하기

입력: arr[] = {5, 1, 2, 8, 3, 4, 1}

출력: 3

설명:

arr[0] + arr[1] + arr[2] = arr[4] + arr[5] + arr[6]

=> 5 + 1 + 2 = 3 + 4 + 1

=> 8 = 8

인덱스 3의 값인 8 자체는 합산에서 제외되며, 그 앞 요소들의 합과 뒤 요소들의 합이 동일하므로 3이 평형 인덱스가 됩니다.

해결 접근 방식

가장 단순한 방법은 배열의 각 요소를 하나씩 확인하면서 해당 위치가 평형 인덱스가 될 수 있는지 검사하는 것입니다.

이를 위해 중첩 반복문(nested loop)을 사용합니다. 외부 반복문은 배열의 각 요소를 순회하고, 내부 반복문은 현재 요소를 기준으로 왼쪽 부분의 합(prevSum)과 오른쪽 부분의 합(nextSum)을 각각 계산하여 두 값이 같은지 비교합니다.

이 방법의 시간 복잡도는 O(n²)입니다.

솔루션 구현 예제

#include <bits/stdc++.h>
using namespace std;

int findEquilibriumIndex(int arr[], int n)
{
    int prevSum, nextSum;

    for (int i = 0; i < n; ++i) {

        prevSum = 0;
        for (int j = 0; j < i; j++)
            prevSum += arr[j];
        nextSum = 0;
        for (int j = i + 1; j < n; j++)
            nextSum += arr[j];

        if (prevSum == nextSum)
            return i;
    }
    return -1;
}

int main() {

    int arr[] = {5, 1, 2, 8, 3, 4, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The equilibrium index is "<<findEquilibriumIndex(arr, n);
    return 0;
}

출력 −

The equilibrium index is 3

효율적인 개선 방법 (O(n))

위 방법은 시간 복잡도가 O(n²)이므로 배열의 크기가 클 경우 비효율적일 수 있습니다. 배열의 전체 합(totalSum)을 미리 계산해 둔 후, 배열을 한 번만 순회하면서 왼쪽 합(leftSum)을 누적시키면 오른쪽 합은 'totalSum − leftSum − 현재 요소'라는 한 번의 연산으로 구할 수 있습니다. 이렇게 하면 시간 복잡도를 O(n)까지 줄일 수 있어 더 큰 입력에서도 효율적으로 동작합니다.