카운팅 정렬 (Counting Sort) - BOJ 10989

배열 원소의 값 == 해당 index의 개수

 

카운팅 정렬은 배열의 index에 의미를 부여하는 방식

 

사용하는 이유 : 많은 탐색이 필요한 상황에서 탐색의 횟수를 줄여주기 때문이다.

주로 사용되는 곳 : 무언가를 "기록"할 때, 카운트할 때, 존재를 확인할 때 주로 사용된다.

못 사용하는 경우 : 문자열을 기록할 때, 정수외의 값을 index로 사용할 때

 

만약 입력이 2,1,4,2,3,5,5,4,4 이라면, cnt 배열은 다음과 같다.

cnt[0]	cnt[1]	cnt[2]	cnt[3]	cnt[4]	cnt[5]
0	1	2	1	3	2

 

 

이중 반복을 이용해 중복이 있는 N개의 수를 빠르게 정렬할 수 있다. 

Ex)

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

10989번: 수 정렬하기 3

#include <iostream>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n, m;
    cin >> n;
    int cnt[10001] = {0};
    for (int i = 0; i < n; i++)
    {
        cin >> m;
        cnt[m]++;
    }

    for (int i = 0; i < 10001; i++)
    {
        for (int j = 0; j < cnt[i]; j++)
        {
            cout << i << '\n';
        }
    }
}