백준 10989번 _ counting sort (c++)

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

10989번: 수 정렬하기 3

이 문제는 우리가 아는 정렬알고리즘들로는 웬만하면 모두 메모리초과가 날 것이라고 감히 확신해본다.
10000이하의 수라고 했으니 short로 배열을 만든다해도 주어진 10,000,000개를 저장할 수 있는 배열만 만들어도, 대략 20Mb가 되어버린다.
애초에 메모리제한이 8Mb라는 건, 우리가 아는 배열에 저장해서 nlogn의 시간복잡도로 계산하는 그런 문제가 아니란 뜻!

그렇다면 해결책은 바로 counting sort이다.
쉽게 말해서 크기 10000의 배열을 만든 다음, 각 index가 몇 번 input되었는지 세는(count) 방법이다.
그리고 count된만큼 해당 숫자를 오름차순으로 출력해주면 다음과 같은 코드가 된다.

#include <iostream>
#include <array>
using namespace std;

void Print(array<int, 10001> &arr) // input 된 수만큼 print하는 함수.
{
    for (int i=0; i<10001; i++) 
    {
        if (arr[i] != 0)
        {
            for (int j=0; j<arr[i]; j++) {cout << i <<'\n';}
        }
    }
}

int main(){
    std::ios_base::sync_with_stdio(false); // cin cout에 걸리는 시간을 줄여줌
    int num, input;
    array<int, 10001> NUM;
    NUM.fill(0); // 배열 0으로 초기화
    cin>>num;
    for (int i=0; i<num; i++)
    {
        cin>>input;
        NUM[input]++; //input을 받을 때마다 1씩 늘려줌
    }
    Print(NUM);
}

 

끝!