백준 10989 (수 정렬하기 3) c++

문제

10989번: 수 정렬하기 3

단순히 수를 오름차순으로 정렬하는 문제입니다.

하지만 틀렸습니다...

 

문제의 제한사항을 보면 메모리 제한이 8 MB 입니다.

또한 숫자가 들어올 수 있는 개수는 10000000개 입니다.

따라서 int 형으로 수를 받게 되면 

최악의 경우 4 byte * 10^7 = 40MB 의 크기가 됩니다.

 

수의 개수는 100000000이지만 수의 범위는 10000까지 입니다. 

따라서 수의 범위의 해당하는 배열의 크기를 잡고 입력되는 수의 index에 다가 세어줍니다.

 

이제 차례대로 출력해주면 됩니다.

---

전체코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>
#include <tuple>
#define MAX 2100000000
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[10001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        arr[a]++;
    }
    for (int i = 1; i <= 10000; i++) {
        if (arr[i] == 0)
            continue;
        for (int j = 0; j < arr[i]; j++)
            cout << i << '\n';
    }
    
    return 0;
}