[백준/C] 10989 - 수 정렬하기 3

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

구현 과정

처음에 compare 함수와 qsort 함수를 사용해 정렬하는 방식으로 구현했는데, 시간초과가 떴다. 알고 보니 계수 정렬을 이용해 구현해야 되는 문제였다.

계수 정렬(counting sort)

계수 정렬은 정수나 정수로 표현할 수 있는 자료를 정렬할 때 사용하는 방법이다. 각 항목이 몇 번 등장했는지를 count하고, count를 기준으로 해당 항목의 위치를 결정한다.

정리하자면, 배열의 [해당 숫자] 인덱스에 그 숫자가 몇 번 등장했는지를 저장하는 것이다!

이를 위해 숫자를 입력받을 때마다 바로 count[해당 숫자]++ 해준다.

for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        count[num]++;
    }

모두 입력받은 후에는 이중 for문을 사용한다.
두번째 for문을 for (int j = 0; j < count[i]; j++) 이라고 쓰는 이유는 해당 숫자가 등장한 만큼 출력해주기 위해서이다. count[i] 에는 정수 i가 등장한 횟수가 저장되어 있다는 것을 기억해야 한다.

for (int i = 0; i < 10001; i++) {
        for (int j = 0; j < count[i]; j++) {
            printf("%d\n", i);
        }
    }

전체 코드

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

int main() {
    int n;
    scanf("%d", &n);

    int *count = (int *)malloc(10001 * sizeof(int));

    for (int i = 0; i < n; i++) {
        int num;
        scanf("%d", &num);
        count[num]++;
    }

    for (int i = 0; i < 10001; i++) {
        for (int j = 0; j < count[i]; j++) {
            printf("%d\n", i);
        }
    }

    free(count);
    return 0;
}