C++로 구현하는 배열 분할 문제: 왼쪽 합과 오른쪽 합이 같아지는 기준 요소 찾기

문제 개요

n개의 요소를 가진 배열 A가 주어졌을 때, 이 배열을 두 개의 부분 배열로 나누되 각 부분 배열의 합이 서로 같아지도록 하는 분할 기준 요소(partition element)를 찾는 것이 목표입니다.

예를 들어 배열 A = [2, 3, 4, 1, 4, 5]가 있다고 가정해 보겠습니다. 이 경우 정답은 1입니다. 왜냐하면 1을 기준으로 앞부분은 [2, 3, 4](합계 9), 뒷부분은 [4, 5](합계 9)로 나뉘어 양쪽의 합이 동일하기 때문입니다.

접근 방법

이 문제는 다음과 같은 단계로 효율적으로 해결할 수 있습니다.

먼저 첫 번째 요소를 제외한 나머지 전체 요소의 합을 right_sum에 저장합니다. 그다음 배열을 왼쪽에서 오른쪽으로 순회하면서, 현재 위치의 요소를 right_sum에서 빼고 left_sum에 더합니다. 이 과정을 반복하다가 left_sum과 right_sum이 같아지는 시점을 찾으면, 그 지점 바로 다음 요소가 분할 기준 요소가 됩니다. 끝까지 순회했는데도 조건을 만족하는 지점이 없다면 -1을 반환하여 분할이 불가능함을 알립니다.

이 방식은 각 위치마다 부분 배열의 합을 매번 새로 계산하는 대신 누적합을 활용하기 때문에, 시간 복잡도가 O(n)으로 매우 효율적입니다.

C++ 구현 예제

#include<iostream>
using namespace std;

int getPartitionElement(int arr[], int size) {
    int right = 0, left = 0;
    // 첫 번째 요소를 제외한 나머지 합을 right에 저장
    for (int i = 1; i < size; i++)
        right += arr[i];
    // 왼쪽에서 오른쪽으로 순회하며 균형 지점 탐색
    for (int i = 0, j = 1; j < size; i++, j++) {
        right -= arr[j];
        left += arr[i];
        if (left == right)
            return arr[i + 1];
    }
    return -1;
}

int main() {
    int arr[] = { 2, 3, 4, 1, 4, 5 };
    int size = sizeof(arr) / sizeof(arr[0]);
    cout << "Partition element: " << getPartitionElement(arr, size);
}

실행 결과

Partition element: 1

동작 원리 살펴보기

배열 [2, 3, 4, 1, 4, 5]를 예로 들어 코드의 흐름을 추적해 보겠습니다. 초기 상태에서 right는 17(3+4+1+4+5), left는 0입니다.

순회가 진행되면 첫 단계에서 left는 2가 되고 right는 14가 됩니다. 다음 단계에서 left는 5, right는 10이 됩니다. 세 번째 단계에서 left는 9, right는 9가 되어 두 값이 일치하고, 이때 함수는 해당 위치 다음 요소인 1을 반환합니다.

마무리

이 알고리즘은 누적합을 활용해 한 번의 순회만으로 답을 구할 수 있어 O(n)의 시간 복잡도와 O(1)의 공간 복잡도를 가집니다. 배열의 균형 분할 지점을 찾아야 하는 다양한 응용 문제에서 유용하게 활용할 수 있는 패턴이므로, 누적합 기반 탐색 기법과 함께 익혀두면 좋습니다.