[10989번][실5] 수 정렬하기 3 (카운팅 정렬)

카운팅 정렬을 사용하라고 했는데 뭔지 몰라서 찾아봄. 카운팅 정렬은 입력되는 숫자의 범위가 작을 때 유용.

 

카운딩 정렬이란?

  숫자 범위만큼 배열을 만들고, 해당 숫자를 인덱스로 써서 숫자가 각각 몇번 나왔는지를 카운팅 함.

  예를들어, 1112334445 라는 배열이 있다면

  int numAry[6] = {0,3,1,2,3,1}

  이렇게 0부터 숫자가 몇번 나왔는지를 셈.

  그리고 나온 횟수만큼 해당 숫자를 출력함.

 

카운팅 정렬 장단점

  장점: 시간 복잡도가 O(n)이다. (quick sort가 nlogn )

  단점: 세는 숫자의 범위만큼 배열이 필요해서, 숫자의 범위가 넓다면 엄청난 메모리가 낭비됨.

 

내 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	const int maxNum = 10001;
	int numAry[maxNum] = {0};
	int numSize;
	int num;

	scanf("%d", &numSize);
	
	/*숫자가 몇번 나왔는지 세기*/
	for (int i = 0; i < numSize; i++) {
		scanf("%d", &num);
		numAry[num]++;
	}

	/*나온 횟수만큼 숫자 출력*/
	for (int i = 0; i < maxNum; i++) {
		for (int j = 0; j < numAry[i]; j++) {
			printf("%d\n", i);
		}
	}

	return 0;
}

 

10989번: 수 정렬하기 3 (acmicpc.net)