C++로 주어진 연산 수행 후 배열에서 같은 숫자의 최대 개수 구하기

정수로 이루어진 배열이 주어졌을 때, 주어진 연산을 수행한 후 배열 안에서 서로 같아질 수 있는 숫자의 최대 개수를 구하는 것이 목표입니다.

문제 조건

i != j를 만족하는 두 원소 a[i]와 a[j]를 선택합니다.
a[i]는 1 증가시키고, a[j]는 1 감소시킵니다 (a[i]++, a[j]--).

핵심 아이디어

배열 원소들의 합(sum)을 구한 뒤, 원소 개수(N)로 나누어 나머지를 확인하면 됩니다.

sum % N == 0 이면 → 모든 원소를 같은 값으로 만들 수 있으므로 정답은 N입니다.
sum % N != 0 이면 → 최소 한 개의 원소는 다른 값을 가질 수밖에 없으므로 정답은 N-1입니다.

증감 연산을 반복해도 배열 전체의 합은 변하지 않기 때문에, 합이 원소 개수로 균등하게 나누어지는지만 판단하면 됩니다.

입력 예제 1

Arr[] = { 1, 2, 3 }

출력 예제 1

같은 숫자의 최대 개수 : 3

설명 − 첫 번째 단계 후 Arr[] = { 2, 2, 2 }가 됩니다. (1을 증가시키고 3을 감소시킴) 원소들의 합은 1+2+3=6이고, 6%3==0이므로 같은 숫자의 개수는 3입니다.

입력 예제 2

Arr[] = { 1, 2, 4 }

출력 예제 2

같은 숫자의 최대 개수 : 2

설명 − 첫 번째 단계 후 Arr[] = { 1, 3, 3 }이 됩니다. (2를 증가시키고 4를 감소시킴) 원소들의 합은 1+2+4=7이고, 7%3==1이므로 같은 숫자의 개수는 3-1=2입니다.

알고리즘 접근 방법

정수 배열 Arr[]에 정수들을 저장합니다.
정수 변수 'size'에 배열의 길이를 저장합니다.
함수 maxEqual(int arr[], int n)은 배열과 그 크기를 입력으로 받아, 주어진 연산 적용 후 배열에 존재할 수 있는 같은 숫자의 최대 개수를 반환합니다.
먼저 배열 원소들의 합을 계산하여 'sum'에 저장합니다.
sum이 size n으로 나누어 떨어지는지 확인합니다 (sum%n==0).
나누어 떨어지면 n을 반환합니다.
그렇지 않으면 n-1을 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
int maxEqual(int arr[], int n){
    int sum = 0;
    for (int i = 0; i < n; i++){
        sum += arr[i];
    }
    if (sum%n==0){
        return n;
    }
    return n-1;
}
int main(){
    int Arr[] = { 1, 4, 1, 2};
    // 배열의 크기
    int size =4;
    cout <<" Maximum count of equal numbers :"<< maxEqual(Arr,size);
    return 0;
}

실행 결과

Maximum count of equal numbers: 4

위 코드에서 배열 { 1, 4, 1, 2 }의 합은 8이고, 8%4==0이므로 모든 원소를 값 2로 만들 수 있어 결과는 4가 됩니다. 시간 복잡도는 O(n)으로, 배열을 한 번만 순회하면 되기 때문에 매우 효율적입니다.