BOJ 2751 : 수 정렬하기 2 with 계수 정렬 (Counting Sort)

알고리즘 문제 전체 링크

 

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

 

 

주어지는 숫자가 -1,000,000 ~ 1,000,000이기 때문에 0 ~ 2,000,000으로 바꾼다.

그리고 a[0 ~ 2,000,000]에는 각 원소의 개수를 증가시키고,

출력할 때는 작은 값부터 원소의 개수만큼 출력하고 다음으로 넘어간다.

#include <stdio.h>

#define MINUS (1000000)

int N;
int a[1000000 + MINUS + 1000];

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

	for (int i = 0; i < N; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		a[tmp + MINUS]++;
	}
	
	for (int i = 0; i <= 1000000 + MINUS; i++)
	{
		while (a[i])
		{
			printf("%d\n", i - MINUS);
			a[i]--;
		}
	}

	return 0;
}