(C++) 백준 11728번 - 배열 합치기

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

11728번: 배열 합치기

문제 풀이

Merge Sort를 활용하여 풀이하였다.

이미 병합할 배열들이 정렬되어 있기에 두 배열의 최솟값을 비교하여 더 작은 최솟값을 출력하는 방식으로 풀이하였다.

#include <iostream>

using namespace std;

int a[1000001];
int b[1000001];
int n, m, tmp, ida, idb;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);  

    cin >> n >> m;

    for(int i = 0; i < n; i++){
        cin >> tmp;
        a[i] = tmp;
    }
    for(int i = 0; i < m; i++){
        cin >> tmp;
        b[i] = tmp;
    }
    for(int i = 0; i < m+n; i++){ // 모든 배열의 요소들을 정렬할 때까지 반복
        if(ida == n) while(idb != m){ // a 배열을 모두 출력했다면 남은 b 배열을 모두 출력
            cout << b[idb++] << " ";
            i++;
        }
        else if(idb == m) while(ida != n){ // b 배열을 모두 출력했다면 남은 a 배열을 모두 출력
            cout << a[ida++] << " ";
            i++;
        } 
        // a배열의 요소와 b배열의 요소를 비교하여 더 적은 요소를 먼저 출력
        else if(a[ida] <= b[idb]) cout << a[ida++] << " "; 
        else if(b[idb] < a[ida]) cout << b[idb++] << " ";
    }
}