[C언어] 백준 10989 : 수 정렬하기 3

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html 카운팅 정렬 예시
https://soobarkbar.tistory.com/101 카운팅 정렬 이해

위의 예시로 풀이를 해보자면 5 2 3 1 4 2 4 5 1 7의 숫자들이 있다. 여기서 각 숫자의 빈도수를 계산하여 배열에 집어 넣는다.

0 1 2 3 4 5 6 7
0 2 2 1 2 2 0 1

이렇게 빈도수를 구 할 수 있다. 그리고 이 빈도수를 토대로 0에서 순차 탐색을 진행하면 된다.

0은 빈도수가 0, 패스

1은 빈도수가 2, 1을 두 번 출력

2는 빈도수가 2, 2를 두 번 출력

3은 빈도수가 1, 3을 한 번 출력

4는 빈도수가 2, 4를 두 번 출력

5는 빈도수가 2, 5를 두 번 출력

6은 빈도수가 0, 패스

7은 빈도수가 1, 7을 한 번 출력

배웠던 것 처럼 누적합을 구하는 방식으로도 할 수 있지만, 이 문제에서는 메모리제한으로 안되는걸 확인했다.

그래서 위 방법대로 진행한다.

https://kindload-save.tistory.com/49 아이디어 참조

풀이

#include <stdio.h>

int arr[10001];
int main()
{
    int n, j;
    int ins;
    scanf("%d", &n);
    int i = 1;
    while(i <= n)
    {
        scanf("%d", &ins);
        arr[ins]++;
        i++;
    }
    i = 1;
    while(i <= 10000)
    {
        j = 1;
        while(j <= arr[i])
        {
            printf("%d\n", i);
            j++;
        }
        i++;
    }
}