[백준] 10989

수 정렬하기 3

문제

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

입력

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

출력

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

풀이

#include <stdio.h>
#include <stdlib.h>

int main(void) {
    int n;
    int *arr;
    int tmp;

    scanf("%d\n", &n);
    arr = (int *)malloc(sizeof(int) * 10001);
    for (int i = 0; i < n; i++) {
        scanf("%d\n", &tmp);
        arr[tmp]++;
    }
    for (int i = 0; i < 10001; i++) {
        while (arr[i]-- > 0) printf("%d\n", i);
    }
}

반성회

배열을 N개만큼 할당하면 메모리가 무조건 초과되기때문에 (메모리 제한이 8메가다)

수의 범위가 0부터 10000임을 이용해서 배열을 10001개만큼 할당한 후 등장하는 수의 개수를 세면 된다

자바스크립트는 메모리 제한을 이길 수가 없어서 C, C++나 파이썬으로만 풀어야 함