서로 크기가 다른 k개의 정렬된 배열이 주어졌을 때, 이 배열들을 모두 병합하여 하나의 정렬된 결과를 출력하는 문제입니다.
예를 들어 k = 3이고 배열이 {2, 4}, {3, 5, 7}, {1, 10, 11, 12}라면, 병합 후 출력 결과는 다음과 같습니다.
1 2 3 4 5 7 10 11 12
해결 접근 방식
이 문제는 최소 힙(Min-Heap) 기반의 우선순위 큐(priority queue)를 활용하면 효율적으로 해결할 수 있습니다. 각 배열의 첫 번째 원소를 힙에 넣고, 가장 작은 값을 꺼낼 때마다 해당 원소가 속한 배열의 다음 원소를 힙에 추가하는 방식입니다.
구체적인 알고리즘은 다음과 같습니다.
- 첫 번째 요소는 정수, 두 번째 요소는 정수 쌍(pair)으로 구성된 pair 타입을 정의합니다(ppi). 여기서 정수 쌍은 각각 배열의 인덱스와 해당 배열 내 원소의 인덱스를 나타냅니다.
- 결과를 저장할 벡터 op를 선언합니다.
- 오름차순으로 동작하는 우선순위 큐(최소 힙) q를 선언합니다.
- i := 0부터 시작하여 i가 배열의 개수보다 작을 동안 반복하며, 각 배열의 첫 번째 원소 (arr[i][0], {i, 0})를 큐에 삽입합니다.
- 큐가 빌 때까지 다음 과정을 반복합니다.
- 큐의 최상단 원소를 current_element로 가져온 뒤 제거합니다.
- current_element에서 배열 인덱스 i와 원소 인덱스 j를 추출합니다.
- current_element의 첫 번째 값(실제 데이터)을 op의 끝에 추가합니다.
- j + 1이 arr[i]의 크기보다 작다면, 즉 해당 배열에 아직 남은 원소가 있다면 (arr[i][j+1], {i, j+1})을 큐에 삽입합니다.
- 모든 반복이 끝나면 병합된 결과 op를 반환합니다.
예제 코드
아래는 위 알고리즘을 C++로 구현한 예제입니다.
#include <bits/stdc++.h>
using namespace std;
#define ppi pair<int,pair<int,int>>
vector<int> merge(vector<vector<int>> arr){
vector<int> op;
priority_queue<ppi, vector<ppi>, greater<ppi>> queue;
for (int i = 0; i < arr.size(); i++)
queue.push({ arr[i][0], { i, 0 } });
while (queue.empty() == false) {
ppi current_element = queue.top();
queue.pop();
int i = current_element.second.first;
int j = current_element.second.second;
op.push_back(current_element.first);
if (j + 1 < arr[i].size())
queue.push({ arr[i][j + 1], { i, j + 1 } });
}
return op;
}
int main(){
vector<vector<int>> arr{ { 2,4 }, { 3,5,7 }, { 1, 10, 11, 12 } };
vector<int> output = merge(arr);
for(int i = 0; i < output.size(); i++)
cout << output[i] << " ";
}입력
{{ 2,4 }, { 3,5,7 }, { 1, 10, 11, 12 }}출력
1 2 3 4 5 7 10 11 12
시간 복잡도 분석
전체 원소의 개수를 N, 배열의 개수를 k라고 할 때, 모든 원소가 한 번씩 힙에 삽입되고 제거되므로 시간 복잡도는 O(N log k)입니다. 단순히 모든 배열을 하나로 합친 뒤 정렬하는 O(N log N) 방식보다 배열의 개수 k가 작을 경우 더 효율적이며, 공간 복잡도는 힙에 항상 최대 k개의 원소만 유지되므로 O(k)입니다.