[백준]10989-수 정렬하기 3(설명X)

#include <cstdio>
 
int main() {
    int input;
    scanf("%d", &input);
    int number[10001]{ 0, };
    for (int i = 0; i < input; i++) {
        int num;
        scanf("%d", &num);
        number[num]++;
    }
    for (int i = 1; i <= 10000; i++) {
        for (int j = 0; j < number[i]; j++)
            printf("%d\n", i);
    }
}

그냥 퀵소트나 머지소트 돌리면 메모리 초과뜬다.

문제에서 10000이하의 자연수만 입력된다고 했으니까, 위와 같이 배열을 만들어두고 입력될때마다 카운팅하면 된다.

 

근데 요즘은 메모리복잡도에 대해서는 별로 신경 안쓰는 분위기이긴 한데..