[백준/BOJ] 2751번 수 정렬하기 2 (C/C++)

백준 온라인 저지(BOJ) 2751번 수 정렬하기 2

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

2751번: 수 정렬하기 2

* 사용언어 : C언어, C++

 

1. 문제

N 개의 수를 오름차순 정렬 [1 ~ 1,000,000]

모든 수의 절대값은 1,000,000 보다 작거나 같음 (중복 X)

 

2. 풀이

O(nlogn) 시간 복잡도인 정렬 알고리즘으로 풀 수 있는 문제입니다.

Merge Sort 를 학습한 뒤 코드를 익히면서 문제를 풀었습니다.

 

Merge Sort 의 아주 기본적인 형태의 코드를 사용하면

응용하지 않고도 풀 수 있는 문제입니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
2751_수 정렬하기 2
https://www.acmicpc.net/problem/2751
*/
#include <cstdio>

const int LM = 1000000;
int a[LM + 5], t[LM + 5], n;

void mSort(int s, int e) {
	if (s >= e) return;

	int m = (s + e) / 2;
	mSort(s, m);
	mSort(m + 1, e);

	int i = s, j = m + 1, k = s;
	while (i <= m && j <= e) {
		if (a[i] <= a[j]) t[k++] = a[i++];
		else t[k++] = a[j++];
	}

	while (i <= m) t[k++] = a[i++];
	while (j <= e) t[k++] = a[j++];

	for (i = s; i <= e; ++i) a[i] = t[i];
}

int main(){
#ifdef _WIN32
	freopen("2751.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) scanf("%d", &a[i]);

	mSort(0, n - 1);
	for (int i = 0; i < n; ++i) printf("%d\n", a[i]);

	return 0;
}