[BOJ알고리즘, C++]#11728_배열 합치기, 정렬, 병합 정렬

 

#1. 문제

11728번: 배열 합치기

 

---

 

#2. 풀이

 

1. 병합 정렬

[알고리즘]#3_정렬 알고리즘

 

[정의] : 병합 정렬은 분할-정복 기반의 정렬 알고리즘입니다. 병합 정렬은 주어진 배열을 두 개의 작은 부분 배열로 분할하고, 각 부분 배열을 재귀적으로 정렬하여 최종적으로 두 배열을 하나의 배열로 병합하여 하나의 정렬된 배열을 얻는 정렬 알고리즘입니다.

[성능] : 병합 정렬의 최악 시간 복잡도는 O(n log n)입니다. 비교적 효율적인 정렬 알고리즘이지만, 정렬 과정에서 추가적인 메모리 공간이 필요합니다.

 

2. 병합 정렬의 기본 개념! 

1. 깊게 생각할 필요 없이, 병합 정렬의 수행 과정 중 두 부분 배열을 비교 연산 후 하나의 배열로 병합하는 작업만 수행해 주면 됩니다.
2. 이미 정렬된 두 배열은 서로를 비교한 후, 나머지 원소들은 차례대로 배열에 삽입해주면 되겠습니다.

 

---

 

#3. 코드

 

#include <iostream>
#include <vector>
#include <string>
using namespace std;

typedef long long ll;

int N, M;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    vector<int> arr1(N);
    vector<int> arr2(M);

    for (int i = 0; i < N; ++i)
    {
        cin >> arr1[i];
    }

    for (int i = 0; i < M; ++i)
    {
        cin >> arr2[i];
    }

    vector<int> res(N + M);

    int leftIdx = 0;
    int rightIdx = 0;
    int resIdx = 0;

    while (leftIdx < N && rightIdx < M)
    {
        if (arr1[leftIdx] < arr2[rightIdx])
        {
            res[resIdx++] = arr1[leftIdx++];
        }
        else
        {
            res[resIdx++] = arr2[rightIdx++];
        }
    }

    while (leftIdx < N)
    {
        res[resIdx++] = arr1[leftIdx++];
    }

    while (rightIdx < M)
    {
        res[resIdx++] = arr2[rightIdx++];
    }

    for (int i = 0; i < N + M; ++i)
        cout << res[i] << ' ';

    return 0;
}

 

---