BOJ 10989번 수 정렬하기 3

BOJ : https://www.acmicpc.net/problem/10989

 

시간제한 3초, 메모리 제한 8MB

최대 1천만개의 수를 이 시간과 메모리안에 정렬할려면 사실상 sort를 쓰거나 

sort보다 더 빠른 함수를 만들더라도 불가능할 것이다..

 

이 문제는 최대의 수가 10000 이라는 것이 힌트이다.

1 2 3 4 5 6 ,,, 9998 9999 10000 이라는 숫자가 1천만개 나올 것이므로

배열[10001] 에 나오는 숫자마다 +1 해주어서 카운트 해두고

1부터 1만까지 차례대로 출력해주면 되는 문제이다.

 

#include <iostream>
using namespace std;
 
int arr[10001], num;
 
int main() {
    ios::sync_with_stdio(false);
    int N; cin >> N;
 
    for (int i = 0; i < N; i++) {
        cin >> num;
        arr[num]++;
    }
 
    for (int i = 1; i < 10001; i++) {
        while (arr[i]) {
            cout << i << '\n';
            arr[i]--;
        }
    }
 
    return 0;
}