문제 정의
정렬된 두 개의 배열이 주어졌을 때, 이 두 배열을 하나의 정렬된 배열로 병합하는 함수를 작성하는 것이 목표입니다.
Arr1[] = {10, 15, 17, 20}
Arr2[] = {5, 9, 13, 19}
Result[] = {5, 9, 10, 13, 15, 17, 19, 20}알고리즘
두 배열이 이미 각각 정렬되어 있다는 점을 활용하면, 투 포인터(Two Pointer) 기법으로 선형 시간 안에 병합할 수 있습니다.
1. 두 배열을 동시에 순회한다 1.1. arr1[i] < arr2[j]인 경우 1.1.1. 결과 배열에 arr1[i]를 추가 1.1.2. 인덱스 'i'와 결과 배열 인덱스 'k'를 증가 1.2. 그렇지 않은 경우(arr2[j] ≤ arr1[i]) 1.2.1. 결과 배열에 arr2[j]를 추가 1.2.2. 인덱스 'j'와 결과 배열 인덱스 'k'를 증가 2. 어느 한쪽 배열의 모든 요소가 처리될 때까지 반복 3. 남은 배열의 나머지 요소들을 결과 배열에 그대로 복사 4. 병합된 결과 배열을 반환
예제 코드
다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
// 두 개의 정렬된 배열을 하나로 병합하는 함수
void mergeSortedArrays(int *arr1, int n1, int *arr2, int n2, int *result){
int i = 0;
int j = 0;
int k = 0;
// 두 배열을 비교하며 작은 값부터 결과 배열에 저장
while (i < n1 && j < n2) {
if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
// 첫 번째 배열에 남은 요소 복사
while (i < n1) {
result[k++] = arr1[i++];
}
// 두 번째 배열에 남은 요소 복사
while (j < n2) {
result[k++] = arr2[j++];
}
}
// 배열을 출력하는 함수
void displayArray(int *arr, int n){
for (int i = 0; i < n; ++i) {
cout << arr[i] << " ";
}
cout << endl;
}
int main(){
int arr1[] = {10, 15, 17, 20};
int arr2[] = {5, 9, 13, 19};
int result[SIZE(arr1) + SIZE(arr2)];
cout << "첫 번째 정렬 배열:" << endl;
displayArray(arr1, SIZE(arr1));
cout << "두 번째 정렬 배열:" << endl;
displayArray(arr2, SIZE(arr2));
mergeSortedArrays(arr1, SIZE(arr1), arr2, SIZE(arr2), result);
cout << "병합 후 최종 배열:" << endl;
displayArray(result, SIZE(result));
return 0;
}출력 결과
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
첫 번째 정렬 배열: 10 15 17 20 두 번째 정렬 배열: 5 9 13 19 병합 후 최종 배열: 5 9 10 13 15 17 19 20
복잡도 분석
- 시간 복잡도: O(n + m) — 두 배열의 길이를 각각 n, m이라 할 때, 모든 요소를 한 번씩만 비교·복사합니다.
- 공간 복잡도: O(n + m) — 병합된 결과를 저장하기 위해 크기가 n + m인 새 배열이 필요합니다.
참고 사항
이 병합 기법은 정렬 알고리즘 중 하나인 합병 정렬(Merge Sort)의 핵심 단계로도 사용됩니다. 입력 배열이 반드시 오름차순으로 정렬되어 있어야 올바른 결과를 얻을 수 있으므로, 구현 전에 입력 데이터의 정렬 여부를 확인하는 것이 좋습니다.