백준 10989번 문제 ( 수 정렬하기 3 )

문제 출처 : https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

이번 문제는 평소에 알고있던 정렬과는 다른 정렬을 사용하였다. 

문제를 읽고 시간 제한과 메모리 제한이 다른 문제와 다르다는 것을 알고 어떻게 해결하면 좋을지에 대한 생각을 했다.

해당 문제에서는 들어오는 테스트 케이스의 수는 10,000,000개 인데 수는 10,000 이하의 수였다.

그래서 배열을 만개 정도만 잡고 카운트 형식으로 풀어보았는데 이것이 계수 정렬 ( Counting Sort ) 이라는 것을

배우게 되었다. 

 

#include<stdio.h>
#pragma warning(disable:4996)
int arr[10001];
int main()
{
    int N;
    int num;
    int count;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &num);
        arr[num]++;
    }
    for (int i = 1; i <= 10000; i++)
    {
        if (arr[i] == 0)
            continue;
        else
        {
            count = arr[i];
            for (int j = 0; j < count; j++)
                printf("%d\n", i);
        }
    }
}