BOJ 10989: 수 정렬하기 3

✔ 문제 링크

BOJ 10989: 수 정렬하기 3

✔ 해결과정

1 ≤ N ≤ 10,000,000인데 메모리 제한이 8MB다. 배열 사이즈를 10,000,000로 잡으면 40MB여서 바로 out이다. 문제에서 각각의 수가 10,000보다 작거나 같은 자연수라고 했으므로 크기 10,001인 배열을 잡고 각각의 수가 몇 번 나왔는지 세고 정렬하는 방식으로 해결할 수 있다.

✔ 정답 Code

#include <bits/stdc++.h>
using namespace std;

int arr[10001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    while(n--) {
        int k;
        cin >> k;
        arr[k]++;
    }

    for(int i=1;i<10001;i++) {
        if(arr[i]!=0) {
            for(int j=0;j<arr[i];j++) {
                cout << i << '\n';
            }
        }
    }
}