[백준 11728] 배열 합치기

배열을 합치는 데, 병합정렬(Merge Sort)를 사용하였다.

별로 어렵지 않은 문제였다.

문제: https://www.acmicpc.net/problem/11728

문제

정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000)

둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 10⁹보다 작거나 같은 정수이다.

출력

첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

예제 입력 1

2 2
3 5
2 9

예제 출력 1

2 3 5 

예제 입력 2

2 1
4 7
1

예제 출력 2

1 4 7

예제 입력 3

4 3
2 3 5 9
1 4 7

예제 출력 3

1 2 3 4 5 7 9

설명

a = [3,5]

b = [2,9]

// a[i]와 b[j]를 비교하여 작은 순서대로 c[k]에 삽입

while(i<n && j<m){
        if(a[i] < b[j])
            c[k++] = a[i++];       
        else
            c[k++] = b[j++];
    }
   

// 위 코드는 i와 j에서 하나라도 배열의 끝까지 가게 되면 반복문이 끝난다.

// 남은 배열을 차례대로 c[k++]에 삽입

   while(i<n)
        c[k++] = a[i++];
    while(j<m)
        c[k++] = b[j++];

#include<iostream>
 
using namespace std;
 
int main(){
    int n,m;
    cin >> n >> m;
    
    int *a = new int[n];
    int *b = new int[m];
    int *c = new int[n+m];
    
    for(int i = 0; i < n; i++)
        cin >> a[i];
    for(int i = 0; i < m; i++)
        cin >> b[i];
    
    int i=0,j=0,k=0;
    
    while(i<n && j<m){
        if(a[i] < b[j])
            c[k++] = a[i++];        
        else
            c[k++] = b[j++];
    }
    
    while(i<n)
        c[k++] = a[i++];
    while(j<m)
        c[k++] = b[j++];
    
    for(int i = 0; i < n+m; i++)
        cout << c[i] << ' ';
    cout << '\n';
 
    return 0;
}

※ 본 글은 개인 포트폴리오 혹은 공부용으로 사용하기 때문에, 무단 복사 유포는 금지하지만, 개인 공부 용도로는 얼마든지 사용하셔도 좋습니다.