C++로 배열의 모든 요소를 동일하게 만드는 데 필요한 연산 횟수 구하기

이 문제에서는 크기가 n인 배열 arr가 주어지며, 우리의 과제는 배열의 모든 요소를 동일하게 만드는 데 필요한 연산 횟수를 구하는 것입니다.

여기서 '연산'은 배열에서 가장 큰 값을 가진 요소로부터 나머지 모든 요소에 가중치를 균등하게 분배하는 작업으로 정의됩니다.

만약 배열의 모든 요소를 동일하게 만드는 것이 불가능하다면 -1을 출력해야 합니다.

예시로 이해하기

입력 : arr[] = {7, 3, 3, 3}
출력 : 3

설명

연산을 수행한 후의 배열은 {4, 4, 4, 4}가 됩니다. 즉, 총 3번의 연산을 거쳐 모든 요소가 4로 일치하게 되는 것입니다.

해결 접근 방법

이 문제를 해결하는 가장 간단한 방법은 먼저 배열에서 최댓값과 최솟값을 찾는 것입니다. 그런 다음 최댓값과 최솟값의 차이를 기준으로, 가중치를 균등하게 분배했을 때 모든 요소가 동일한 값으로 수렴할 수 있는지 확인합니다. 조건이 만족되면 필요한 연산 횟수를 반환하고, 만족되지 않으면 -1을 반환하여 해당 배열의 요소들을 동일하게 만드는 것이 불가능함을 나타냅니다.

구현 예제

#include<bits/stdc++.h>
using namespace std;
int findOperationCount(int arr[], int n){
    int j = 0, operations = 0;
    int maxVal = arr[0];
    int minVal = arr[0];
    int maxValInd = 0;
    for (int i = 1; i < n; i++){
        if(arr[i] > maxVal){
            maxVal = arr[i];
            maxValInd = i;
        }
        if(arr[i] < minVal){
            minVal = arr[i];
        }
    }
    for (int i = 0; i < n; i++){
        if (arr[i] != maxVal && arr[i] <= minVal && arr[i] != 0){
            arr[j] += 1;
            arr[maxValInd] -= 1;
            maxVal -= 1;
            operations += 1;
            j += 1;
        }
        else if (arr[i] != 0){
            j += 1;
        }
    }
    for (int i = 0; i < n; i++){
        if (arr[i] != maxVal){
            operations = -1;
            break;
        }
    }
    return operations;
}
int main(){
    int arr[] = {4, 4, 8, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout<<"모든 배열 요소를 동일하게 만드는 데 필요한 연산 횟수는 "<<findOperationCount(arr, n);
    return 0;
}

출력

모든 배열 요소를 동일하게 만드는 데 필요한 연산 횟수는 3

복잡도 분석

위 코드는 배열을 몇 차례 순회하면서 연산을 수행하므로 시간 복잡도는 O(n)입니다. 또한 입력 배열 외에 추가적인 메모리를 사용하지 않기 때문에 공간 복잡도는 O(1)입니다.