10989

10989

10989번 문제

카운팅 정렬(counting sort)은 숫자를 세어 그 수만큼 차례로 정렬하는 알고리즘이다(출처)

#include 
#define MAX 10000 // 개수
#define MAX_NUM 10000 // 크기

int main(void) {
	int arr[MAX+1], count[MAX_NUM+1], newArr[MAX+1], sum[MAX_NUM+1], i, n;

	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &arr[i]); // 숫자 입력 받기
		count[arr[i]]++; // 숫자 개수 카운팅
	}
	sum[0] = 0;
	for (i = 1; i <= MAX_NUM; i++) {
		sum[i] = sum[i - 1] + count[i]; // 개수의 누적합 구하기
	}
	for (i = n; i >= 1; i--) {
		newArr[sum[arr[i]]] = arr[i]; // 마지막 원소부터 새로운 정렬에 배열한다
		sum[arr[i]]--; // 누적합의 개수를 줄인다
	}
	for (i = 1; i <= n; i++)
		printf("%d\n", newArr[i]); // 출력한다
}

출처의 그림을 참고하여 작성하였다. 우선 숫자를 입력 받고 개수를 카운팅한다. 카운팅 받은 개수를 합하면서 숫자의 개수의 누적합을 구한다. 마지막 원소부터 새로운 배열에 정렬한다. 정렬하고 나면 누적합의 개수를 하나 줄인다. 이렇게 하면 새롭게 정렬할 수 있다. 다만 알고리즘을 구현하면서 당황스러웠던 점은 MAX를 정의했을 때 10,000,000라고 하면 실행이 되지 않는다는 점이었다. 또한 배열들의 개수가 MAX개인 경우에는 배열을 선언할 때 MAX+1로 해야한다는 점을 까먹어서 계속 실행이 되지 않았었다. 주의하자.

결과