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

문제 정의

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

예시

입력 배열이 {1, 2, 3, 4}라고 가정해 보겠습니다. 이 경우 모든 요소를 같은 값으로 만들기 위해 최소 3번의 연산이 필요합니다. 예를 들어, 값이 1인 요소에 3을 더해 4로 만들면 나머지 요소(4)와 값이 일치하게 됩니다.

접근 방법 및 알고리즘

핵심 아이디어는 다음과 같습니다. 이미 값이 같은 요소들은 추가 연산 없이 그대로 두고, 나머지 요소만 원하는 값으로 변경하면 됩니다. 따라서 가장 많이 등장하는 값(최대 빈도)을 기준으로 삼는 것이 유리합니다.

1. 배열에서 가장 많이 등장하는 요소의 빈도를 구합니다. 이 값을 'x'라고 합시다.
2. 전체 요소 개수가 n이므로, 이미 x개의 요소는 목표 값과 일치합니다. 따라서 남은 (n - x)개의 요소에 대해서만 연산을 수행하면 됩니다.

즉, 정답은 n - 최대 빈도가 됩니다. 빈도 계산에는 해시 맵(unordered_map)을 활용하면 효율적입니다.

C++ 구현 코드

#include <bits/stdc++.h>
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) — 최악의 경우 모든 요소가 서로 다른 값을 가질 때 해시 맵에 n개의 항목이 저장됩니다.