[백준/c++] 10989번 - 수 정렬하기3

문제

문제

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

입력

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

출력

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

제한

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

풀이과정

1.규칙

• 정렬 갯수 N(1 ≤ N ≤ 10,000,000)이 매우 크므로 메모리와 시간을 고려합니다.
• 정렬 해야하는 수들은 10,000보다 작거나 같은 자연수라는 범위안에 있습니다.

2.순서

최소한의 메모리로! 최대한 빠르게! 가 문제의 핵심이었습니다.

c++의 경우 10,000,000크기의 배열이나 벡터는 무조건 '메모리초과'가 뜨므로, 제가 좋아하는 머지소트를 쓸 수 없었습니다.

대신, 특정범위 안에 있는 수들을 정렬할때 가장 빠른 시간복잡도$O(N+k)$와 공간복잡도$O(k)$를 가지는 Counting sort(계수 정렬)기법을 사용해서 풀었습니다.

<참고1>

-Counting sort 위키 : https://en.wikipedia.org/wiki/Counting_sort

-Counting sort를 잘 정리해 놓으신 분의 글👍 : https://bowbowbow.tistory.com/8

<참고2>

-Merge sort의 평균 시간복잡도 : $O(NlogN)$

-Merge sort의 공간복잡도 : $О(N)$

3.코드

* 최대한 빠른속도여야 하므로, 입출력도 cin, cout보다 빠른 scanf, printf로 해주어야 정답처리가 됩니다. *