[백준/BOJ] 10989번 수 정렬하기 3 (C++)

www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

입력값이 최대 10,000,000 이라서 시간복잡도가 O(NlogN)인 병합정렬을 이용해서 문제를 먼저 해결했다가 메모리 초과가 발생했습니다. 그래서 시간 복잡도와 공간 복잡도 모두를 만족할 수 있는 방법이 무엇이 있을까 검색을 해본 결과 계수 정렬을 이용하면 이 문제를 해결할 수 있다는 것을 알게 되었습니다. 

 

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

vector<int> v(10001);

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, maxx = 0;
    cin>>n;
    
    for(int i = 0; i < n; i++) {
        int x;
        cin>>x;
        v[x]++;
        maxx = max(maxx, x);
    }
    
    for(int i = 1; i <= maxx; i++) {
        for(int j = 0; j < v[i]; j++) {
            cout<<i<<"\n";
        }
    }
}