[BOJ]11728번: 배열 합치기 (c++)

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

11728번: 배열 합치기

 

병합

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	// 입력
	int N, M;
	cin >> N >> M;
	vector<int> A(N);
	vector<int> B(M);
	for (int i = 0; i < N; ++i)
	{
		cin >> A[i];
	}
	for (int i = 0; i < M; ++i)
	{
		cin >> B[i];
	}

	/*
		병합

		두 배열 A, B는 이미 정렬되어 있으므로,
		A, B의 요소를 앞에서부터 비교하여 더 작은수를 먼저 벡터 V에 넣어준다.
	*/
	vector<int> V(N + M);
	int A_idx = 0, B_idx = 0, v_i = 0;

	while (A_idx < N && B_idx < M)
	{
		if (A[A_idx] <= B[B_idx])
		{
			V[v_i++] = A[A_idx++];
		}
		else
		{
			V[v_i++] = B[B_idx++];
		}
	}

	// 비교 후 A, B에 남은 요소가 있다면 마저 V에 넣어준다
	while (A_idx < N)
	{
		V[v_i++] = A[A_idx++];
	}
	while (B_idx < M)
	{
		V[v_i++] = B[B_idx++];
	}

	// 출력
	for (int i : V)
	{
		cout << i << ' ';
	}

	return 0;
}

 

 

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

 

두 배열이 이미 정렬되어 있으므로, 병합만 실행하면 된다.

병합 정렬(Merge Sort)에서 병합 알고리즘만 가져다 쓰면 된다.

 

풀이과정은 다음과 같다.

1. 두 벡터의 요소를 앞에서부터 비교하여, 더 작은 요소를 먼저 결과벡터 V에 넣는 동작을 반복한다.

(어느 한쪽의 인덱스가 끝에 다다를때 까지)

2. 남은 요소가 있으면 마저 결과벡터 V에 넣어준다. 

 

 

 

 

병합정렬을 참고한 페이지

Challenge: Implement merge | 병합 정렬 | 칸아카데미

 

7. 병합 정렬(Merge Sort)