C++로 배열 요소를 합쳐 모든 값이 K 이상이 될 때까지 만드는 최소 연산 횟수 구하기

문제 개요

정렬되지 않은 배열 arr[]와 정수 K가 주어집니다. 우리는 배열의 두 요소를 선택해 더한 후 하나의 요소로 합치는 연산을 수행할 수 있으며, 이 연산을 반복하여 배열의 모든 요소가 K 이상이 되도록 만들어야 합니다. 목표는 이때 필요한 최소 연산 횟수를 구하는 것입니다.

예제

입력: arr[] = {1 10 12 9 2 3}, K = 6
출력: 2

풀이 설명

먼저 가장 작은 두 요소 (1 + 2)를 더하면 새로운 배열은 {3, 10, 12, 9, 3}이 됩니다.
다음으로 남아 있는 두 개의 작은 값 (3 + 3)을 더하면 배열은 {6, 10, 12, 9}가 됩니다.
이 시점에서 배열의 모든 요소가 K(6) 이상임을 확인할 수 있습니다. 따라서 총 2번의 연산이 필요하며, 출력은 2입니다.

알고리즘 접근 방식: 최소 힙(Min Heap) 활용

이 문제는 그리디(Greedy) 기법과 최소 힙(Min Heap) 자료구조를 함께 사용하면 효율적으로 해결할 수 있습니다.

배열의 모든 요소를 최소 힙에 삽입합니다.
힙의 루트(최솟값)가 K보다 작은 동안 아래 과정을 반복합니다:
1. 힙에서 가장 작은 두 요소를 추출합니다.
2. 두 값을 더한 결과를 다시 힙에 삽입합니다.
3. 연산 횟수를 1 증가시킵니다.
힙에 요소가 하나만 남았는데도 그 값이 K보다 작다면, 더 이상 연산으로 조건을 만족시킬 수 없으므로 -1을 반환합니다.

매번 가장 작은 두 값을 합치는 것이 최적의 전략입니다. 작은 값들을 빠르게 키워야 전체 조건을 충족하는 데 필요한 연산 횟수를 최소화할 수 있기 때문입니다.

C++ 코드

#include <bits/stdc++.h>
using namespace std;
class MinHeap {
   int *harr;
   int capacity;
   int heap_size;
   public:
   MinHeap(int *arr, int capacity);
   void heapify(int );
   int parent(int i) {
      return (i-1)/2;
   }
   int left(int i) {
      return (2*i + 1);
   }
   int right(int i) {
      return (2*i + 2);
   }
   int extractMin();
   int getMin() {
      return harr[0];
   }
   int getSize() {
      return heap_size;
   }
   void insertKey(int k);
};
MinHeap::MinHeap(int arr[], int n) {
   heap_size = n;
   capacity = n;
   harr = new int[n];
   for (int i=0; i<n; i++)
      harr[i] = arr[i];
   for (int i=n/2-1; i>=0; i--)
      heapify(i);
}
void MinHeap::insertKey(int k) {
   heap_size++;
   int i = heap_size - 1;
   harr[i] = k;
   while (i != 0 && harr[parent(i)] > harr[i]) {
      swap(harr[i], harr[parent(i)]);
      i = parent(i);
   }
}
int MinHeap::extractMin() {
   if (heap_size <= 0)
      return INT_MAX;
   if (heap_size == 1) {
      heap_size--;
      return harr[0];
   }
   int root = harr[0];
   harr[0] = harr[heap_size-1];
   heap_size--;
   heapify(0);
   return root;
}
void MinHeap::heapify(int i) {
   int l = left(i);
   int r = right(i);
   int smallest = i;
   if (l < heap_size && harr[l] < harr[i])
      smallest = l;
   if (r < heap_size && harr[r] < harr[smallest])
      smallest = r;
   if (smallest != i) {
      swap(harr[i], harr[smallest]);
      heapify(smallest);
   }
}
int countMinOps(int arr[], int n, int k) {
   MinHeap h(arr, n);
   long int res = 0;
   while (h.getMin() < k) {
      if (h.getSize() == 1)
         return -1;
      int first = h.extractMin();
      int second = h.extractMin();
      h.insertKey(first + second);
      res++;
   }
   return res;
}
int main() {
   int arr[] = {1, 10, 12, 9, 2, 3};
   int n = sizeof(arr)/sizeof(arr[0]);
   int k = 6;
   cout << countMinOps(arr, n, k);
   return 0;
}

실행 결과

시간 복잡도 분석

최소 힙에서 요소를 삽입하거나 추출하는 연산은 각각 O(log N)의 시간이 소요됩니다. 최악의 경우 연산은 최대 N-1번까지 발생할 수 있으므로, 이 알고리즘의 전체 시간 복잡도는 O(N log N)입니다. 또한 힙은 배열을 그대로 사용해 구현되므로 추가 공간 복잡도는 O(N)입니다.