C++로 배열의 모든 요소를 동일하게 만들기 위한 최소 삭제 연산 구하기

문제 설명

n개의 요소로 이루어진 배열이 주어지며, 요소는 중복될 수 있습니다. 배열에서 임의의 개수만큼 요소를 삭제할 수 있을 때, 배열의 모든 요소를 동일하게 만들기 위해 삭제해야 하는 최소 요소 개수를 구하는 것이 목표입니다.

arr[] = {10, 8, 10, 7, 10, -1, -4, 12}

위 예시에서는 가장 많이 등장하는 값인 10을 제외한 나머지 5개의 요소를 삭제해야 배열의 모든 요소가 동일해집니다.

알고리즘

핵심 아이디어는 간단합니다. 가장 자주 등장하는 요소를 남기고 나머지를 모두 삭제하면 되므로, 전체 배열 크기에서 최대 빈도수를 뺀 값이 곧 최소 삭제 횟수입니다.

1. 각 요소의 빈도수를 계산합니다.
2. 빈도수 중 최댓값을 찾습니다. 이를 maxFrequency라고 합니다.
3. 삭제해야 할 요소의 개수 = n – maxFrequency (n은 배열의 크기)

이 알고리즘은 해시 맵(unordered_map)을 사용하면 시간 복잡도 O(n), 공간 복잡도 O(n)으로 효율적으로 해결할 수 있습니다.

예제 코드

#include <iostream>
#include <unordered_map>
#include <climits>
#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))
using namespace std;
int minDeleteOperations(int *arr, int n){
   unordered_map<int, int> frequecy;
   int maxFrequency = INT_MIN;
   for (int i = 0; i < n; ++i) {
      frequecy[arr[i]]++;
   }
   for (auto it = frequecy.begin(); it != frequecy.end(); ++it) {
      maxFrequency = max(maxFrequency, it->second);
   }
   return (n - maxFrequency);
}
int main(){
   int arr[] = {10, 8, 10, 7, 10, -1, 9, 4};
   cout << "Required deletes: " << minDeleteOperations(arr, SIZE(arr)) << "
";
   return 0;
}

코드 설명

minDeleteOperations 함수는 먼저 unordered_map을 사용해 배열 내 각 요소의 빈도수를 기록합니다. 그다음 반복자를 순회하며 가장 높은 빈도수(maxFrequency)를 찾습니다. 마지막으로 배열의 전체 크기 n에서 maxFrequency를 빼서 반환하면, 이 값이 모든 요소를 동일하게 만들기 위해 필요한 최소 삭제 횟수입니다.

출력 결과

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

Required deletes: 5

예제 배열 {10, 8, 10, 7, 10, -1, 9, 4}에서 10은 세 번 등장하므로 최대 빈도수는 3이고, 배열 크기가 8이므로 8 − 3 = 5개의 요소를 삭제하면 됩니다.