C++에서 배열 균형을 맞추기 위해 더해야 할 최솟값 구하기

문제 소개

n개의 요소를 가진 배열 A가 있다고 가정해 보겠습니다. 이때 n은 짝수입니다. 우리의 목표는 이 배열의 균형을 맞추기 위해 필요한 값을 구하는 것입니다. 배열의 크기가 짝수이므로 배열을 두 개의 절반으로 나눌 수 있으며, 왼쪽 절반의 합과 오른쪽 절반의 합이 서로 같아지도록 만들어야 합니다.

예를 들어 배열이 A = [1, 2, 3, 2, 5, 3]이라고 해보겠습니다. 왼쪽 절반(1 + 2 + 3)의 합은 6이고, 오른쪽 절반(2 + 5 + 3)의 합은 10입니다. 따라서 양쪽의 합이 같아지려면 합이 작은 쪽에 4를 더해야 합니다.

접근 방법

이 문제의 풀이법은 매우 간단합니다. 배열의 첫 번째 절반과 두 번째 절반의 합을 각각 구한 뒤, 두 값의 차이에 절댓값을 취해서 반환하면 그 값이 곧 균형을 맞추기 위해 필요한 숫자가 됩니다.

알고리즘 단계

1. 인덱스 0부터 n/2 - 1까지의 요소를 모두 더해 왼쪽 절반의 합(left_sum)을 구합니다.
2. 인덱스 n/2부터 n - 1까지의 요소를 모두 더해 오른쪽 절반의 합(right_sum)을 구합니다.
3. 두 합의 차이에 절댓값(abs)을 적용한 결과를 반환합니다.

C++ 구현 예제

#include<iostream>
#include<cmath>
using namespace std;
int getValueToBalance(int a[], int n) {
    int left_sum = 0;
    for (int i = 0; i < n/2; i++)
        left_sum += a[i];
    int right_sum = 0;
    for (int i = n/2; i < n; i++)
        right_sum += a[i];
    return abs(left_sum - right_sum);
}
int main() {
    int arr[] = {1, 2, 3, 2, 5, 3};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "균형을 위한 숫자: " << getValueToBalance(arr, n);
}

위 코드에서 getValueToBalance 함수는 반복문 두 개를 사용해 각각의 절반에 속한 요소들의 합을 계산하고, abs() 함수를 통해 두 합의 절댓값 차이를 반환합니다. main 함수에서는 예제 배열을 선언한 뒤 이 함수를 호출해 결과를 출력합니다.

실행 결과

균형을 위한 숫자: 4

시간 및 공간 복잡도

시간 복잡도: O(n) — 배열의 모든 요소를 정확히 한 번씩 순회합니다.
공간 복잡도: O(1) — 추가적인 자료구조 없이 몇 개의 변수만 사용하므로 상수 크기의 메모리만 필요합니다.