[ C++ ] #11728 배열 합치기 ( 실버 V )

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

11728번: 배열 합치기

---

문제

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

입력

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

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

출력

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

 

---

풀이

이것은 merge sort의 기초같은 문제이다.

정렬된 두 배열이 있고 이들을 merge하며 sort해야한다.

각각 맨 앞의 요소들을 비교해가면서 하나씩 넣으면된다.

#include <iostream>

using namespace std;

int N, M;
int one[1000000];
int two[1000000];
int MergeArray[2000000];

int main(){

    ios::sync_with_stdio(0);
    cin.tie(nullptr);

    cin>>N>>M; //두 배열의 크기

    //배열 입력받기
    for(int i=0;i<N;i++){
        cin>>one[i];
    }
    for(int i=0;i<M;i++){
        cin>>two[i];
    }

    int nn=0; //N의 offset
    int mm=0; //M의 offset

    for(int i=0;i<N+M;i++){  //정렬

        if(one[nn]<two[mm]){ //1번 배열이 더 작다면

            MergeArray[i]=one[nn++];
            
            if(nn==N){  //1번 배열을 모두 읽었다면
                int start=mm;
                for(int j=start;j<M;j++){  //2번배열로 merge배열 채우기
                    MergeArray[++i]=two[j];
                }
                break;
            }

        }else{  //2번 배열이 더 작다면

            MergeArray[i]=two[mm++];
            
            if(mm==M){  //2번 배열을 모두 읽었다면
                int start=nn;
                for(int j=start;j<N;j++){  //1번배열로 merge배열 채우기
                    MergeArray[++i]=one[j];
                }
                break;
            }
        }
    }

    //출력
    for(int i=0;i<N+M;i++){

        cout<<MergeArray[i]<<" ";

    }
    
}