배열(Array)이란?
배열은 동일한 데이터 타입의 요소들을 담는 컨테이너이며, 각 요소는 0부터 시작하는 인덱스로 접근할 수 있습니다.
이번 문제에서는 정수형 배열을 사용하여, 배열의 모든 요소가 주어진 숫자 k보다 크거나 같은지 확인합니다. 만약 조건을 만족하지 않는다면, 배열에서 가장 작은 두 요소를 꺼내 더한 뒤 그 합을 하나의 새로운 요소로 취급합니다. 이후 새로운 배열에 대해 동일한 조건을 다시 검사하고, 모든 요소가 조건을 충족하면 지금까지 수행한 덧셈 연산의 횟수를 반환합니다.
예시
Array = { 2, 6, 3, 12, 7 }, K = 5
Output : 1설명 − 먼저 배열의 모든 요소가 k 이상인지 확인합니다. 아직 조건을 만족하지 않으므로 가장 작은 두 수인 2와 3을 더해 5를 만들고, 이 값을 새 배열의 첫 번째 요소로 삽입합니다. 다시 조건을 검사하면 이번에는 모든 요소가 5 이상이므로, 수행한 덧셈 횟수인 1을 반환합니다.
알고리즘
입력 − 배열과 k 값
Step 1 : 모든 요소가 k보다 크거나 같은지 확인한다.
Step 2 : if(참){
반복 횟수를 출력한다.
}
exit(0)
Step 3 : else {
배열에서 가장 작은 두 요소를 더해 하나의 요소로 만든다.
}
Step 4 : Step 1로 돌아간다.
효율적인 접근: 최소 힙(Min Heap)
이 알고리즘은 매 반복마다 배열에서 가장 작은 두 요소를 빠르게 찾아야 합니다. 단순히 배열을 정렬하거나 전체를 탐색하면 비효율적이므로, 항상 최솟값을 O(1) 시간에 조회하고 삽입·삭제를 O(log n)에 처리할 수 있는 최소 힙(Min Heap) 자료구조를 사용하는 것이 효율적입니다. 또한 힙에 요소가 하나만 남았는데도 여전히 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 main(){
int arr[] = { 2, 6,3,12, 7};
int n = sizeof(arr)/sizeof(arr[0]);
int k = 5;
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++;
}
cout << res;
return 0;
}
출력 결과
1
위 코드는 입력 배열 {2, 6, 3, 12, 7}과 k=5에 대해, 가장 작은 두 요소인 2와 3을 한 번 더해 5를 만들면 모든 요소가 5 이상이 되므로 연산 횟수 1을 출력합니다.