[백준 / 10989] (C++) 수 정렬하기 3

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

 

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

 

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

 

코드

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

int main(void) {
	int N;
	int arr[10001] = { 0, };

	scanf("%d", &N);

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

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


}

이 문제는 꽤 신박하다. N의 최대수가 10^7으로 꽤 큰 편에 추가적인 조건으로 수들이 10000보다 작거나 같은 숫자들이라 한다.

O(nlogn)의 시간복잡도로 풀면은 꽤 아슬아슬하게 갈 것 같긴 하지만 이 방법은 좀 아닌듯하다...

또한 N의 크기로 볼 때 저 어마어마한 숫자들을 다 저장하면 메모리 초과가 나올 것이다.

그렇다면 10000보다 작거나 같다는 조건을 사용해야 할텐데.... 이 문제의 힌트로 Counting sort라는 것을 보았다.

그래서 Counting Sort를 구글링하여 찾아본 결과 처음보는 정렬을 볼 수 있었고 바로 코딩하여 해봤지만 메모리 초과가 나왔다....

(counting sort 참고 :  https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html)

그래서 다시 구글링해 본 결과 그냥 단순한 알고리즘이었던 것이다....

나온 횟수를 배열에 저장하여 인덱스 순서대로 다시 출력하면 되는 간단한 알고리즘이었다.

 

다만 이 정렬알고리즘은 숫자들의 최대 크기(여기선 10000)에 종속되기 때문에 최대 크기가 작을때만 성공 적으로 동작 할 수 있다.