백준] 11728 - 배열 합치기

시간 제한 : 1.5초

메모리 제한 : 256MB

입력

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

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

출력

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

소스코드

#include <iostream>
#include <vector>
using namespace std;
int main(void)
{
	ios_base::sync_with_stdio(false);
	int m, n, idx1, idx2;
	cin >> n >> m;
	vector<int> arr1(n), arr2(m), ans(n+m);
	for (int i = 0; i < n; i++)
		cin >> arr1[i];
	for (int i = 0; i < m; i++)
		cin >> arr2[i];

	idx1 = idx2 = 0;
	for (int i = 0; i < n + m; i++)
	{
		if (idx1 >= n)
			ans[i] = arr2[idx2++];
		else if (idx2 >= m)
			ans[i] = arr1[idx1++];
		else {
			if (arr1[idx1] < arr2[idx2])
				ans[i] = arr1[idx1++];
			else
				ans[i] = arr2[idx2++];
		}
	}
	for (int i = 0; i < n + m; i++)
		cout << ans[i] << ' ';
}

Tip

Merge Sort(합병 정렬)을 응용하는 문제로 두 배열의 요소끼리 비교하면서 하나의 배열을 완성하는 간단한 문제다.