백준 수 정렬하기 3

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

10989번: 수 정렬하기 3

---

문제

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

---

입력

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

출력

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

---

5 초 (하단 참고)

8 MB (하단 참고)

164037

37704

28185

23.410%

 

이 문제는 메모리 제한이 8MB라 일반적인 정렬 방식(algorithm sort 등)을 사용하면 메모리 초과가 뜬다.

N개의 수가 주어지는데 N개의 수의 범위가 10,000보다 작거나 같은 자연수이다.

(0부터 10,000까지)

 

이 경우 0부터 10000까지 표현하는 배열 하나를 만들면 해결 할 수 있었다.

 

예를 들어서, 표의 윗부분이 입력받은 수 그 자체이고, 밑부분이 입력받은 수의 개수라고 한다면

10개의 입력이 주어지는 예시를 보면 5,2,3,1..이런식으로 숫자가 주어질 때, 해당 숫자의 등장 횟수를

배열에 저장하는 것이다.

 

10
5
2
3
1
4
2
3
5
1
7

0	1	2	3	4	5	6	7	8	9
0	2	2	2	1	2	0	1	0	0

이런식으로 배열에 등장횟수를 저장하고, 0부터 10000까지 해당 숫자를 개수만큼 출력해준다.

 

#include <iostream>
using namespace std;
int main(void){
    int arr[10001] = {0, };
    int n;
    cin >> n;
    for(int i = 0;i<n;i++){
        int x;
        scanf("%d",&x);
        arr[x]++;
    }
    
    for(int i = 0;i<10001;i++){
        for(int j = 0;j<arr[i];j++){
            printf("%d\n",i);
        }
    }
}