10989번_수정렬하기 3

정렬하는 문제이다. 하지만 범위가 N(1 ≤ N ≤ 10,000,000)라 메모리 초과에 조심해야 한다. 그리고 당연히 n^2으로 하면 시간이 터진다. 

vector와 multiset을 이용해봤는데 메모리 초과가 발생했다.

다른 분들꺼를 참고해보니 배열 인덱스를 사용하면 됬다. 값이 10000을 안넘기 때문에 공간은 10000개로 충분했고, 시간도 n으로 되기 때문에 충분했다. 

 

#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
 
int main(void){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n;
    int v[10001];
 
    cin >> n;
    memset(v, 0, sizeof(v));
    for(int i = 0; i < n; i++){
        int num;
        cin >> num;
        v[num]++;
    }
    for(int i = 1; i <= 10000;i++){
        while(v[i]){
            cout << i << "\n";
            v[i]--;
        }
    }
}