Counting Sort (C++)

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

위 문제를 counting sort로 구현해 봤다.

주어지는 수의 절댓값이 1,000,000 이하이기 때문에 배열의 인덱스를 활용할 때 음수 처리를 위해 1000000을 더해준 인덱스에 저장한다.

1의 갯수는 1000001에 저장되는 것이다. 

따라서 출력할 때, 1000000을 빼고 출력해주면 된다.

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int arr[2000001];
bool cmp(int a, int b) {
    return a > b;
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        arr[num + 1000000]++; // 저거 뺴고 출력하면 됨
    }
    for (int i = 0; i <= 2000000; i++) {
        while (arr[i]--)
            cout << i - 1000000 << '\n';
    }
    return 0;
}