백준 10989 - 수 정렬하기 3

문제 링크: https://acmicpc.net/problem/10989 

10989번: 수 정렬하기 3

---

문제를 요약해봅시다.

• 주어진 $N$개의 수를 오름차순으로 정렬하여 출력합니다.

---

문제의 조건을 읽어보면 $N \le 10,000,000$으로 $N$의 제한이 매우 큰 것을 볼 수 있습니다.

이 정도 제한이면 병합 정렬이나 퀵 정렬같은 $O(N \log N)$의 시간복잡도를 갖는 정렬 알고리즘으로는 시간 제한에 맞추지 못할 수 있습니다. 엎친데 덮친 격으로 메모리 제한이 8MB이므로 $10,000,000$개 수를 다 저장하는 위의 알고리즘들로는 메모리 초과가 발생하게 됩니다.

따라서 널리 알려진 방법들은 사용할 수 없습니다. 어떻게 해야 할까요?

 

문제의 핵심은 주어지는 수들의 범위가 구간 $[1, 10000]$에 속한다는 것입니다.

수의 범위가 꽤 작기 때문에 각 수가 몇 번 등장했는지만 세어 주면 문제를 해결할 수 있습니다.

예를 들어 1 5 2 3 4 5 3 3 이 들어온다면 1이 1번, 2가 1번, 3이 3번, 4가 1번, 5가 2번이므로 1 2 3 3 3 4 5 5 를 얻을 수 있습니다.

 

시간복잡도는 입출력을 각각 $N$번 하므로 $O(N)$이고, 공간복잡도는 $O(10000) = O(1)$입니다.

---

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

int main() {
    fastio;
    
    int n;
    cin >> n;
    
    // 각 수가 몇 번 등장했는지 기록하는 배열입니다.
    vector<int> cnt(10001);
    
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        
        cnt[x]++;
    }
    
    // 기록된 횟수만큼 해당 수를 출력합니다.
    for (int i = 1; i <= 10000; i++) {
        for (int j = 0; j < cnt[i]; j++) {
            cout << i << "\n";
        }
    }
}