[C/C++] 백준 - 11728번 : 배열 합치기

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

11728번: 배열 합치기

문제

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

입력

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

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

출력

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

 

이 문제에 대한 풀이는 2개가 존재하는 것 같다.

분할 정복과 투 포인터. 일단 나는 투포인터로 문제를 해결했다.

 

투포인터로 

하나의 포인터는 A의 시작점

또 다른 포인터는 B의 시작점에 둔다.

 

그리고 두 개를 비교하면서 더 작은 것이 존재한다면 그것을 넣고 다음 인덱스로 포인터를 옮겨준다.

만약 두 개의 포인터가 가리키는 값이 같다면 2개 모두 값을 넣어주고 포인터를 하나 옆으로 옮겨준다.

 

근데 주의해야할점이 무작정 포인터만 옮기면, 배열의 크기보다 큰 인덱스에 포인터가 참조할 수도 있다.

이 부분만 주의해서 코드를 작성하면 된다.

#include <iostream>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#include <cstring>
#include <map>
#include <algorithm>
#define ll long long
#define INF 987654321
#define CUNLINK ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define MAX 100000 + 1

using namespace std;

int N, M;

int main() {
	CUNLINK;
	cin >> N >> M;
	vector<int> A(N, 0), B(M, 0);
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < M; i++) cin >> B[i];

	int st = 0, en = 0;
	vector<int> answer;
	while (answer.size() != (N + M)) {
		if (A[st] < B[en]) {
			answer.push_back(A[st++]);
			if (st == N) {
				while (en != M) answer.push_back(B[en++]);
			}
		}
		else if (A[st] > B[en]) {
			answer.push_back(B[en++]);
			if (en == M) {
				while (st != N) answer.push_back(A[st++]);
			}
		}
		else if (A[st] == B[en]) {
			answer.push_back(A[st++]);
			if (st == N) {
				while (en != M) answer.push_back(B[en++]);
			}
			if (en < M) {
				answer.push_back(B[en++]);
				if (en == M) {
					while (st != N) answer.push_back(A[st++]);
				}
			}
		}
	}
	for (auto a : answer) cout << a << " ";

	return 0;
}