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

백준 웹사이트 "10989번 - 수 정렬하기 3" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

10989번: 수 정렬하기 3

---

소스 코드

#include <stdio.h>

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

    // 1. 카운팅 배열 선언/초기화
    int counting[10001];
    for(int i=0; i<10001; i++){
        counting[i] = 0;
    }

    // 2. 카운팅 정렬 (입력)
    for(int i=0; i<N; i++){
        int input;
        scanf("%d", &input);
        counting[input]++;
    }

    // 3. 카운팅 정렬 (출력)
    for(int i=0; i<10001; i++){
        // counting[i] 횟수만큼 i 출력
        for(int j=0; j<counting[i]; j++){   
            printf("%d\n", i);
        }
    }
}

---

문제 풀이

  이번 문제에서 사용되는 카운팅 정렬 (Counting Sort)은 그 어떤 정렬보다도 빠른 \(O(n)\)의 시간 복잡도를 보입니다. 이러한 빠른 속도는 '카운팅 배열'을 미리 선언함으로써 얻어집니다. 입력될 수들의 범위를 사전에 알고 있다면, 그만큼의 크기를 가진 카운팅 배열을 미리 선언하고 수가 입력될 때마다 해당 인덱스의 배열 요소에 기록합니다. 모든 입력이 종료되면 카운팅 배열은 각 숫자가 몇 개씩 존재하는지에 대한 정보를 가지게 되겠죠? 출력 단계에서 카운팅 배열을 참고해서, 각 숫자를 해당 개수만큼씩 출력하면 정렬은 완료됩니다.

  소스 코드도 크게 어렵지 않습니다. 첫 단계는 카운팅 배열을 만드는 단계로, 입력될 수들의 범위가 10,000 이하라는 조건이 주어지므로 10,001의 크기를 가진 카운팅 배열을 선언/초기화합니다. 카운팅 배열 선언을 완료하면, 입력을 받으며 각 숫자를 카운팅 배열에 기록합니다. 최대 인덱스가 정확히 10,000이므로, 어떤 숫자가 입력되어도 그 숫자에 해당하는 인덱스가 존재하여 입력이 가능합니다. 마지막 단계에서는 \(counting\) 배열 수들의 출력을 진행합니다. 인덱스 \(i\)를 각각 \(counting[i]\)회 출력하면 정렬된 숫자들을 볼 수 있습니다.