백준 11728. 배열 합치기

백준 11728. 배열 합치기

투 포인터를 묻는 문제

간단한 문제라 답은 맞았는데, 점점 더 개선할 점이 보여서 기록해둠

1. 간단 설명

---

A의 크기 N, B의 크기 M이 주어진다 (1 ≤ N, M ≤ 1,000,000)

이후 배열 A의 내용과, B의 내용이 쭉 주어진다

각 원소는 10^9보다 작거나 같은 정수

두 배열을 합친 후 정렬한 결과를 출력하면 된다

2. 예제

---

2 2
3 5
2 9

A = [3, 5], B = [2, 9]

정렬하면 2, 3, 5, 9 를 출력

3. 알고리즘

---

내가 생각한 방법

1. A와 B를 정렬한다(이미 정렬되어 주어짐)
2. A와 B에 각각 원소를 가리키는 인덱스를 사용
3. 해당 인덱스를 0부터 배열 끝까지 이동하며 크기를 비교하면서 결과 배열에 넣는다
4. 만약 어느쪽이 먼저 끝에 도달한다면 ,나머지를 모두 결과 배열에 넣기

4. 소스코드

---

1. 첫번째 풀이

벡터를 이용해서, 정렬된 결과를 담을 배열을 만들고, 투포인터를 이용해서 풀이했다

#include <iostream>
#include <vector>

using namespace std;

int N, M;
vector<int> A, B, res;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
    ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		int tmp; cin >> tmp;
		A.push_back(tmp);
	}
	for (int i = 0; i < M; i++) {
		int tmp; cin >> tmp;
		B.push_back(tmp);
	}

	int idx_A = 0, idx_B = 0;

	while (idx_A != N && idx_B != M ) {
		if (A[idx_A] <= B[idx_B]) {
			res.push_back(A[idx_A]);
			idx_A++;
		}
		else {
			res.push_back(B[idx_B]);
			idx_B++;
		}
	}

	// 나머지 처리
	if (idx_A != A.size() ) {
		while (idx_A != N) {
			res.push_back(A[idx_A]);
			idx_A++;
		}
	}

	if (idx_B != B.size() ) {
		while (idx_B != M) {
			res.push_back(B[idx_B]);
			idx_B++;
		}
	}

	for (int e : res) {
		cout << e << " ";
	}

	return 0;
}

1. 두번째 풀이

STL Merge 함수를 이용한 간단한 풀이

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); 

	int N, M;
	cin >> N >> M;
	
	vector<int> A(N), B(M), result(N + M);

	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < M; i++) cin >> B[i];

	// STL Merge() 사용
	merge(A.begin(), A.end(), B.begin(), B.end(), result.begin());

	for (int e : result) {
		cout << e << " ";
	}

	return 0;
}

merge()함수는 STL 알고리즘 헤더에 들어있는 합병 정렬을 수행하는 함수다

정렬된 두 범위를 합쳐서 새로운 벡터로 병합하는 함수

1. 출력 배열을 따로 만들지 않고 바로 출력하는 풀이

#include <iostream>
#include <vector>

using namespace std;

int main() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL); 

	int N, M;
	cin >> N >> M;
	
	vector<int> A(N), B(M);

	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < M; i++) cin >> B[i];

	int i = 0, j = 0;

	while (i < N && j < M) {
		if (A[i] <= B[j]) {
			cout << A[i++] << " ";
		}
		else {
			cout << B[j++] << " ";
		}
	}

	while (i < N) cout << A[i++] << " ";
	while (j < M) cout << B[j++] << " ";

	return 0;
}

res 배열에 결과를 담지 않고, 바로 출력한다

아래서부터 위로 1, 2, 3번 풀이에 사용된 리소스

속도나 메모리면에서 훨씬 효율적인 모습이다