C++ STL의 std::merge() 함수로 두 개의 정렬된 배열을 빠르게 병합하는 방법

이 글에서는 C++ STL의 std::merge() 함수를 사용하여 두 개의 정렬된 배열을 빠르고 효율적으로 병합하는 방법을 알아보겠습니다.

문제를 해결하기에 앞서, 먼저 C++ STL의 std::merge() 함수가 어떤 기능을 하는지 살펴보겠습니다.

std::merge()란 무엇인가?

std::merge()는 C++ STL에 내장된 함수로, <algorithm> 헤더 파일에 정의되어 있습니다. 이 함수는 두 개의 정렬된 범위(range) 또는 시퀀스를 병합하는 데 사용됩니다.

merge()는 두 개의 정렬된 범위를 입력받아 이를 하나의 단일 정렬 범위로 결합합니다. 모든 요소는 '작다'(<) 비교 연산자를 기준으로 비교되기 때문에, 병합된 결과 범위 역시 자체적으로 정렬된 상태를 유지하게 됩니다.

std::merge()로 두 개의 정렬된 배열을 빠르게 병합하는 방법

정렬된 두 배열 arr1[]과 arr2[]가 주어졌을 때, C++ STL에서 제공하는 merge() 함수를 사용해 이 두 배열을 병합하고, 그 결과를 arr3[]와 같은 새로운 빈 배열에 저장하는 것이 목표입니다.

• 먼저 두 배열 arr[size_arr]과 brr[size_brr]의 각각의 크기를 계산한 뒤, 두 크기의 합만큼의 길이를 가진 세 번째 배열 final[size_arr + size_brr]을 선언합니다.

• 그다음 merge(arr, (arr + size_arr), brr, (brr + size_brr), final);과 같은 형태로 merge() 함수를 호출하여 두 배열을 세 번째 배열로 병합합니다.

예제 코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    int arr[] = {1, 2, 3};
    int size_arr = sizeof(arr)/sizeof(arr[0]);
    int brr[] = {4, 5, 6};
    int size_brr = sizeof(brr)/sizeof(brr[0]);
    int final[size_arr + size_brr];
    merge(arr, (arr + size_arr), brr, (brr + size_brr), final);
    cout<<"병합 후 최종 배열: ";
    for (int i = 0; i < (size_brr + size_arr); i++)
        cout << final[i] << " ";
    return 0;
}

실행 결과

병합 후 최종 배열: 1 2 3 4 5 6

위 예제에서 볼 수 있듯이, std::merge()를 사용하면 직접 병합 알고리즘을 구현하지 않고도 몇 줄의 코드만으로 두 개의 정렬된 배열을 손쉽게 하나의 정렬된 배열로 합칠 수 있습니다. 이는 코드의 가독성을 높이고 실수 가능성을 줄여주므로, 정렬된 데이터를 다룰 때 매우 유용하게 활용할 수 있습니다.