기수 정렬(radix sort)

기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음

해당 자릿수만 비교

 

시간 복잡도는 O(kn), k는 데이터의 자릿수

 

기수 정렬은 시간 복잡도가 가장 짧은 정렬이다!

코테에서 정렬해야 하는 데이터 개수가 너무 많으면 기수 정렬을 써보자.

 

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

10989번: 수 정렬하기 3

10,000,000, N이 엄청 크다..

O(nlogn)보다 더 빠른 알고리즘이 필요하다.

 

숫자가 10000보다 작거나 같은 조건을 이용해서 계수 정렬(counting sort)를 사용하자

 

#include <iostream>
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int n;
    cin >> n;
    int count[10001] = { 0 };
    int num = 0;
 
    for (int i = 1; i <= n; i++)
    {
        cin >> num;
        count[num]++;
    }
 
    for (int i = 1; i <= 10000; i++)
    {
        if (count[i] != 0)
        {
            for (int j = 0; j < count[i]; j++)
            {
                cout << i << '\n';
            }
        }
    }
}

이거 안넣어서 시간 초과 나왔다.

그냥 무조건 넣자