BOJ 11728 배열 합치기

문제

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

정렬된 두 배열이 주어지면, 그 두 배열을 병합한 결과를 출력하는 문제이다.

 

풀이

기본적인 머지소트에 필요한 병합 과정이다.

두 배열에서 더 작은 것을 골라 출력하면, 결과적으로 정렬된 배열이 완성된다.

풀이보다는 구현 자체를 익숙해지도록 하자.

 

시간 복잡도 : $O(N+M)$

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define MAXN 1000000

int n, m, a[MAXN+10], b[MAXN+10];

int main()
{
    ios_base::sync_with_stdio(false);
    int i;

    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++) scanf("%d", &a[i]);
    for(i=1; i<=m; i++) scanf("%d", &b[i]);

    int pa = 1, pb = 1;
    while(pa<=n || pb<=m)
    {
        if(pa<=n && (pb>m || a[pa]<b[pb])) printf("%d ", a[pa++]);
        else printf("%d ", b[pb++]);
    }

    return 0;
}