C++ 배열 요소만 사용해 배열 균등화 연산 횟수 구하기

이 문제에서는 n개의 요소로 이루어진 배열이 주어집니다. 우리의 목표는 배열 내부의 요소들만을 사용하여 배열 전체를 균등화하는 데 필요한 연산 횟수를 계산하는 프로그램을 작성하는 것입니다.

여기서 말하는 연산이란 요소의 값을 더하거나 빼는 작업을 의미하며, 배열의 모든 요소를 동일한 값으로 만들기 위해 수행해야 하는 총 연산 횟수를 구해야 합니다.

예제로 문제 이해하기

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

출력: 3

설명:

모든 요소가 맞춰질 균등 값은 2입니다. 이 과정에서 배열의 전체 합은 변하지 않습니다. 먼저 arr[3]의 값에서 1을 옮겨 arr[1]의 값에 더하고, 이어서 arr[0]의 값에서 2를 옮겨 arr[1]의 값에 더합니다.

해결 접근 방식

이 문제를 해결하는 가장 간단한 방법은 배열 전체를 대표하는 균등 값을 하나 정하는 것입니다.

먼저 배열 요소들의 평균을 구해 연산 수행 가능 여부를 판단합니다. 평균이 정수라면 균등화가 가능하고, 정수가 아니라면 균등화는 불가능합니다.

균등화가 가능한 경우에는 필요한 연산 횟수를 계산하여 반환합니다. 이때 연산 횟수는 각 요소와 평균 사이의 절대 차이의 합을 절반으로 나눈 값과 같습니다.

알고리즘

1단계: 배열의 모든 요소의 평균을 구합니다.

2단계: 평균이 정수가 아니라면 -1을 반환하여 균등화가 불가능함을 나타냅니다.

3단계: 평균이 정수라면 각 요소와 평균 사이의 절대 차이를 구합니다.

4단계: 절대 차이의 총합을 절반으로 나눈 값을 결과로 반환합니다.

솔루션 구현 예제

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

int calcEqualisedOperations(int arr[], int n) {
    
    int sum = 0, average, operations = 0;
    for (int i = 0; i < n; i++)
       sum += arr[i];
    if (sum % n != 0)
       return -1;
    average = sum/n;
    for (int i = 0; i < n; i++)
       operations += ( abs(arr[i] - average) / 2 );

    return operations;
}

int main() {

    int arr[] = { 5, 3, 2, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"Operations required to equalize an array using array elements is "<<calcEqualisedOperations(arr, n);
    return 0;
}

출력

Operations required to equalize an array using array elements is 2

코드 설명

calcEqualisedOperations() 함수는 먼저 배열의 총합을 구한 뒤, 총합이 요소 개수 n으로 나누어 떨어지지 않으면 -1을 반환합니다. 나누어 떨어진다면 평균을 계산하고, 각 요소와 평균의 절대 차이를 2로 나눈 값을 모두 더해 필요한 연산 횟수를 구합니다.

위 예제에서 배열 {5, 3, 2, 6}의 총합은 16이고 평균은 4입니다. 각 요소와 평균의 차이는 1, 1, 2, 2이며, 이를 2로 나눈 값들의 합인 2가 곧 필요한 연산 횟수입니다.

시간 복잡도

이 솔루션의 시간 복잡도는 O(n)이며, 추가 메모리 없이 상수 공간 O(1)만 사용하므로 매우 효율적입니다.