C++로 배열의 모든 요소를 같게 만드는 최소 연산 횟수 구하기

문제 설명

n개의 양의 정수로 이루어진 배열이 주어집니다. 우리의 목표는 배열의 모든 요소를 동일한 값으로 만들기 위해 필요한 최소 연산 횟수를 구하는 것입니다. 이때 배열의 각 요소에 대해 덧셈, 뺄셈, 곱셈, 나눗셈 연산을 자유롭게 수행할 수 있습니다.

예시

입력 배열이 {1, 2, 3, 4}라고 가정해 보겠습니다. 모든 요소를 4로 통일하려면 1, 2, 3에 각각 한 번씩 덧셈을 수행하면 되므로, 총 3번의 연산이 필요합니다.

접근 방식 및 알고리즘

이 문제의 핵심은 다음과 같은 직관에서 출발합니다. 이미 값이 같은 요소가 많을수록, 나머지 요소만 바꾸면 되므로 필요한 연산 횟수가 줄어듭니다. 즉, 가장 자주 등장하는 값(최빈값)을 기준으로 삼는 것이 항상 최적입니다.

1. 배열에서 가장 많이 등장하는 값을 선택하고, 그 등장 횟수를 x라고 합니다.
2. 이미 같은 값을 가진 요소가 x개이므로, 나머지 요소들을 한 번씩만 변환하면 됩니다. 따라서 필요한 연산 횟수는 n - x입니다.

C++ 구현 예제

해시 맵(unordered_map)을 사용하면 각 값의 등장 빈도를 O(n) 시간 복잡도로 효율적으로 계산할 수 있습니다.

#include <iostream>
#include <unordered_map>
using namespace std;

int getMinOperations(int *arr, int n) {
    unordered_map<int, int> hash;
    for (int i = 0; i < n; ++i) {
        hash[arr[i]]++;
    }
    int maxFrequency = 0;
    for (auto elem : hash) {
        if (elem.second > maxFrequency) {
            maxFrequency = elem.second;
        }
    }
    return (n - maxFrequency);
}

int main() {
    int arr[] = {1, 2, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Minimum required operations = " <<
        getMinOperations(arr, n) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Minimum required operations = 3

복잡도 분석

시간 복잡도는 배열을 한 번 순회하며 빈도를 계산하고 해시 맵을 다시 순회하므로 O(n)이며, 공간 복잡도는 서로 다른 값의 개수에 비례하여 최악의 경우 O(n)입니다.