백준 2751번 C/C++

www.acmicpc.net/problem/2751

2751번: 수 정렬하기 2

이 문제는 제가 알고리즘 공부에 올렸었던 merge sort를 활용하면 쉽게 풀 수 있습니다.

하지만 제가 올렸던 그대로 merge sort를 사용하면 아마 풀리지 않으실 것입니다.

그 이유는 배열의 크기 때문인데요. 배열의 크기가 충분하지 않아서 그렇습니다.

제가 풀었던 코드는 다음과 같습니다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
int b[10000000];
void merge(int a[], int low, int mid, int high) {		//머지소트
	
	int i = low, j = mid + 1, k = 0;

	while (i <= mid && j <= high) {
		if (a[i] <= a[j]) {
			b[k] = a[i];
			i++;
			k++;
		}
		else {
			b[k] = a[j];
			j++;
			k++;
		}
	}

	while (i <= mid) {
		b[k] = a[i];
		i++;
		k++;
	}

	while (j <= high) {
		b[k] = a[j];
		j++;
		k++;
	}
	k--;
	while (k >= 0) {
		a[low + k] = b[k];
		k--;
	}

}
void mergesort(int a[], int low, int high) {
	if (low < high) {
		int m = (low + high) / 2;

		mergesort(a, low, m);

		mergesort(a, m + 1, high);

		merge(a, low, m, high);
	}
	else {
		return;
	}
}

int su[10000000];
int main()
{
	int n;
	
	scanf("%d", &n);	//수의 개수
	for (int i = 0; i < n; i++) {
		scanf("%d", &su[i]);
	}

	mergesort(su, 0, n-1);

	for (int i = 0; i < n; i++) {
		printf("%d\n", su[i]);
	}

}

 merge sort를 잘 사용할 수 있다면 바로 풀 수 있는 문제였습니다.