백준 11728번: 배열 합치기

두 배열을 합쳐서 정렬한 값을 출력하는 문제입니다.

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

 

앞서 포스팅한 머지소트를 이용하여 간단하게 풀 수 있습니다.

https://inthecar4345.tistory.com/151

합병 정렬 (merge sort)

설명

배열의 크기인 N, M의 최대값이 1,000,000입니다.

두 배열을 합한 크기만큼의 배열을 만들고, 정렬을 위해 사용할 임시 배열을 같은 크기로 잡아줍니다.

#include <stdio.h>

const int LM = 1000000 + 10;
int N, M;
int arr[LM * 2], trr[LM * 2];

 

배열 입력을 받을 때, N + M 크기만큼 루프를 돌면서 arr에 입력을 받고, 그것을 정렬하면 됩니다.

int main() {
	int i;

	scanf("%d %d", &N, &M);	
	for (i = 0; i < N + M; i++) {
		scanf("%d", &arr[i]);
	}

	sort(0, i - 1);

	for (i = 0; i < N + M; i++) printf("%d ", arr[i]);

	return 0;
}

 

머지소트 자체는 이전에 포스팅했던 것과 동일합니다. 

void merge(int start, int end) {
	int mid = (start + end) >> 1;

	int i = start, j = mid + 1, k = start;
	while (i <= mid && j <= end) {
		if (arr[i] < arr[j]) trr[k++] = arr[i++];
		else trr[k++] = arr[j++];
	}
	while (i <= mid) trr[k++] = arr[i++];
	while (j <= end) trr[k++] = arr[j++];

	for (i = start; i <= end; i++) arr[i] = trr[i];
}

void sort(int start, int end) {
	if (start >= end) return;

	int mid = (start + end) >> 1;
	sort(start, mid);
	sort(mid + 1, end);
	merge(start, end);
}

 

정렬된 후, arr를 출력하면 됩니다.

전체 코드

#include <stdio.h>

const int LM = 1000000 + 10;
int N, M;
int arr[LM * 2], trr[LM * 2];

void merge(int start, int end) {
	int mid = (start + end) >> 1;

	int i = start, j = mid + 1, k = start;
	while (i <= mid && j <= end) {
		if (arr[i] < arr[j]) trr[k++] = arr[i++];
		else trr[k++] = arr[j++];
	}
	while (i <= mid) trr[k++] = arr[i++];
	while (j <= end) trr[k++] = arr[j++];

	for (i = start; i <= end; i++) arr[i] = trr[i];
}

void sort(int start, int end) {
	if (start >= end) return;

	int mid = (start + end) >> 1;
	sort(start, mid);
	sort(mid + 1, end);
	merge(start, end);
}

int main() {
	int i;

	scanf("%d %d", &N, &M);	
	for (i = 0; i < N + M; i++) {
		scanf("%d", &arr[i]);
	}

	sort(0, i - 1);

	for (i = 0; i < N + M; i++) printf("%d ", arr[i]);

	return 0;
}