백준 10989 C언어 문제 풀이 - 수 정렬하기 3

문제 이해

이 문제는 주어진 수의 개수가 최대 10,000,000개이므로 일반적인 정렬 알고리즘을 사용해서는 시간 초과가 발생합니다. 따라서, 수의 범위가 1부터 10,000까지이므로, 계수 정렬(Counting Sort) 알고리즘을 사용하여 문제를 해결합니다.

계수 정렬(Counting Sort) 알고리즘

계수 정렬은 입력된 수들의 개수를 셀 때 사용하는 알고리즘입니다. 각 수가 몇 번 등장하는지 세고, 그 수를 오름차순으로 출력하는 방식으로 동작합니다.

예를 들어, 아래와 같은 수열이 주어졌다고 가정해봅시다.

3 1 4 1 5 9 2 6 5 3 5

이 수열을 계수 정렬로 정렬하면, 아래와 같이 수의 개수를 센 뒤, 오름차순으로 출력할 수 있습니다.

1 1 2 3 3 4 5 5 5 6 9  

계수 정렬의 시간 복잡도는 입력 수의 개수를 `N`, 입력 수의 최대값을 `K`라고 했을 때, `O(N+K)`입니다. 이번 문제에서는 `N`이 최대 10,000,000이고 `K`가 10,000이므로 일반적인 정렬 알고리즘보다 빠르게 문제를 해결할 수 있습니다.

문제 해결

이제 주어진 입력 수열을 계수 정렬로 정렬하는 방법에 대해 알아보겠습니다.

#include <stdio.h>

int cnt[10001]; // 입력 수의 개수를 저장할 배열

int main() {
    int n, num;

    scanf("%d", &n);

    // 입력 수의 개수를 카운팅
    for (int i = 0; i < n; i++) {
        scanf("%d", &num);
        cnt[num]++;
    }

    // 정렬된 결과 출력
    for (int i = 1; i <= 10000; i++) {
        for (int j = 0; j < cnt[i]; j++) {
            printf("%d\n", i);
        }
    }

    return 0;
}

```

위 코드에서는 `cnt` 배열을 선언해서 입력 수의 개수를 저장합니다. 이후 입력 수를 읽어들이면서 `cnt` 배열에 해당하는 인덱스에 입력 수의 개수를 증가시킵니다.

그리고 나서, `cnt` 배열을 순회하면서 오름차순으로 정렬된 결과를 출력합니다.