[10989] 수 정렬하기 3 (C++)

#include <iostream>

using namespace std;

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

    int num[10001] = { 0 };
    int tmp;
    int n; cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> tmp;
        num[tmp]++;
    }

    for (int i = 1; i < 10001; i++) {
        for (int j = 0; j < num[i]; j++)
            cout << i << "\n";
    }
    
    return 0;
}

 

1. 메모리 제한 8mb, 수의 개수는 10,000,000개로 vector를 사용하면 메모리 초과

=> O(nlogn)보다 시간복잡도가 낮은 알고리즘을 사용해야 함

2. 배열을 사용하여 입력받은 자연수 index의 값을 증가시켜주는 계수 정렬 알고리즘을 사용