15688 수 정렬하기 5 (C++)

이번에는 정렬 파트의 문제를 풀었다. 시뮬레이션 문제가 너무나도 어려워서 일단은 하나씩 차근차근.

 

일단 이 문제는 단순히 sort() 함수를 가지고 풀 수 있는 문제가 아니었다. 

나 또한 "아 ㅋㅋ sort() 함수 만세!" 하면서 풀다가 시간초과라는 벽을 만나게 됐다.

 

이 문제는 Counting Sort의 원리를 이용하여 풀어야 한다.

 

Counting Sort는 각 자리의 수가 얼마나 있는지 카운트를 하고 배열에 저장 시킨 뒤, 비내림차순일 경우 차례대로 각 배열의 개수만큼 출력 시키면 되는 정렬이다.

 

#include <bits/stdc++.h>
using namespace std;
#define MX 2000001
#define endl '\n'
int freq[MX];
int n;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int m;
    cin >> n;
    for(int i = 0; i < n; i++) {
        int a;
        cin >> a;
        freq[a + 1000000]++;
    }
    int a = 1;
    for(int i = 0; i <= 2000000; i++) {
        while(freq[i]--) {
            cout << i-1000000 << '\n';
        }
    }
}

문제에서  1,000,000 을 제한으로 두고 있고, 절댓값까지 생각하니 배열의 크기를 2배로 잡았다. 

그리고 for 문을 돌때마다 입력하는 수의 배열에 개수를 추가하고, 출력할때는 그 수만큼 출력시키면 되는 것이다.