정렬된 'n'개의 배열이 주어진 상황을 생각해 봅시다. 예를 들어 세 개의 정수형 배열 arr1[], arr2[], arr3[]이 있다고 할 때, 이 모든 배열을 병합하면서 그 결과 배열이 실행 시점(runtime)에 곧바로 정렬된 상태가 되도록 만드는 것이 목표입니다.
예제로 이해하기
입력 −
int a[] = {21, 22, 23, 24};
int b[] = {28, 31, 35};
출력 − int resultant[] = {21, 22, 23, 24, 28, 31, 35}
설명 − 배열의 요소들은 결과 배열에 담기기 전에 서로 비교되며, 각 값에 맞는 적절한 위치에 순서대로 삽입됩니다.
입력 −
int a[] = {1, 3, 5, 7, 9, 11, 13};
int b[] = {14, 16, 18};
int c[] = {19, 20, 21, 22};
출력 − int resultant[] = {1, 3, 5, 7, 9, 11, 13, 14, 16, 18, 19, 20, 21, 22}
설명 − 이 경우에도 배열 요소들을 먼저 비교한 뒤, 결과 배열 안에서 알맞은 자리에 차례대로 배치됩니다.
프로그램의 동작 원리
- 세 개의 정수 배열 arr1[], arr2[], arr3[]과 결과 배열 result[]를 준비하고, mergeSortedArray(new int[][] { arr1, arr2, arr3 }) 메서드를 호출합니다.
- mergeSortedArray 메서드 내부에서는 다음 단계가 수행됩니다.
- 우선순위 큐(PriorityQueue) 타입의 queue 변수와 누적 개수를 저장할 total 변수를 선언하고, total을 0으로 초기화합니다.
- i를 0부터 배열의 길이까지 반복하는 for 루프를 실행하며, 각 배열의 첫 번째 요소를 담은 ArrayBucket 객체를 queue에 추가하고 total에 해당 배열의 길이(arr[i].length)를 더합니다.
- 인덱스 m을 0으로 설정하고 결과를 담을 result[] 정수 배열을 선언합니다.
- queue가 빌 때까지 while 루프를 반복하면서, queue.poll()로 꺼낸 ArrayBucket 객체 ac의 현재 값(ac.arr[ac.index])을 result[m++]에 저장합니다. 이후 ac.index가 ac.arr.length - 1보다 작으면 같은 배열의 다음 인덱스를 가리키는 새 ArrayBucket(ac.arr, ac.index + 1)을 queue에 다시 추가합니다.
- 모든 요소가 처리되면 result 배열을 반환합니다.
우선순위 큐를 사용하는 이유
이 방식은 최소 힙(min-heap) 기반의 우선순위 큐를 활용하기 때문에, 전체 요소 수를 N, 배열의 개수를 k라고 할 때 시간 복잡도가 O(N log k)로 유지됩니다. 매번 큐에서 가장 작은 값을 꺼내 결과 배열에 채워 넣기만 하면 되므로, 별도의 전체 재정렬 과정 없이도 항상 정렬된 결과를 얻을 수 있다는 것이 가장 큰 장점입니다.
예제 코드
import java.util.Arrays;
import java.util.PriorityQueue;
class ArrayBucket implements Comparable<ArrayBucket> {
int[] arr;
int index;
public ArrayBucket(int[] arr, int index){
this.arr = arr;
this.index = index;
}
@Override
public int compareTo(ArrayBucket o){
return this.arr[this.index] - o.arr[o.index];
}
}
public class testClass {
public static int[] mergeSortedArray(int[][] arr){
PriorityQueue<ArrayBucket> queue = new PriorityQueue<ArrayBucket>();
int total = 0;
for (int i = 0; i < arr.length; i++){
queue.add(new ArrayBucket(arr[i], 0));
total = total + arr[i].length;
}
int m = 0;
int result[] = new int[total];
while (!queue.isEmpty()){
ArrayBucket ac = queue.poll();
result[m++] = ac.arr[ac.index];
if (ac.index < ac.arr.length - 1){
queue.add(new ArrayBucket(ac.arr, ac.index + 1));
}
}
return result;
}
public static void main(String[] args){
int[] arr1 = { 1, 3, 5, 7 };
int[] arr2 = { 2, 4, 6, 8 };
int[] arr3 = { 0, 9, 10, 11 };
int[] result = mergeSortedArray(new int[][] { arr1, arr2, arr3 });
System.out.println("The final merged sorted array is :- " + Arrays.toString(result));
}
}
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
The final merged sorted array is :- [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]