C++ 백준 11728번 : 배열 합치기

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

11728번: 배열 합치기

문제

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

입력

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

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

출력

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

---

풀이

단순 두 배열을 합쳐서 sort하는 방법도 있지만 투 포인터를 공부하는 중이니 투포인터로 풀어보았다.

1. 각 배열마다 포인터를 두고 작은 것은 정답 배열에 저장한 후 포인터를 옮겨주는 식.

2. 만약 두 배열 중 한 배열이 끝에 도달하면 나머지 배열을 정답 배열 뒤에 저장

---

#include <bits/stdc++.h>
using namespace std;
int one[1000001] = { 0, };
int two[1000001] = { 0, };
vector <int> ans;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N, M;
	cin >> N >> M;

	int one_p = 1; // 배열포인터
	int two_p = 1; // 배열포인터
	int tmp; // 배열내용
	for (int i = 1; i <= N; i++) {
		cin >> tmp;
		one[i] = tmp;
	}

	for (int i = 1; i <= M; i++) {
		cin >> tmp;
		two[i] = tmp;
	}

	while (one_p != N + 1 && two_p != M + 1) {
		if (one[one_p] <= two[two_p]) { // 배열1이 더 클 경우
			ans.push_back(one[one_p]);
			one_p++;
		}
		else {
			ans.push_back(two[two_p]); // 배열2가 더 클 경우
			two_p++;
		}
	}

	//한쪽이 다 끝났을 경우 while문 break
	if (one_p == N + 1) { // 배열1이 다 끝났을 경우
		for (int j = two_p; j <= M; j++) {
			ans.push_back(two[j]);
		}
	}
	else {
		for (int j = one_p; j <= N; j++) { // 배열2가 다 끝났을 경우
			ans.push_back(one[j]);
		}
	}

	for (int i = 0; i < M + N; i++) {
		cout << ans[i] << " ";
	}


	return 0;
}