[boj 10989] 카운팅 정렬

이 정렬법은 O(n+k)의 시간 복잡도를 가진다.
이때 k는 정렬하고자 하는 수 배열의 최대값이다.

n개의 배열을 한 번 훑으며 개수를 체크해야 하므로O(n)인데
최대값 k에 따라서 메모리가 증가한다.

알고리즘

count배열을 선언한다.
이때 배열의 크기는 정렬하고자 하는 수의 최대값으로 정한다.

#include<cstdio>
#include<cstring>
int main() {
    int n;
    scanf("%d", &n);
    int input;
    int count[10000];
    // 초기화 해야함
    memset(count, 0, 10000*sizeof(int));

    // 입력을 어레이로 받지 않고 단일 int로 받는것에 주의
    for(int i=0;i<n;i++) {
        scanf("%d", &input);
        count[input-1]++;
    }

    // 순서대로 출력
    for(int i=0;i<10000;i++) {
        while(count[i]!=0) {
            printf("%d\n", i+1);
            count[i]--;
        }
    }
}

제한조건

1. 음수가 나오면 인덱스를 쓸 수 없으므로 카운팅정렬을 쓸 수 없다.
2. 정렬하고자 하는 배열의 최대값이 매우 크면 메모리를 왕창 써야한다.