[c++][BOJ] 수 정렬하기 3

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

10989번: 수 정렬하기 3

주어지는 숫자를 정렬하는 문제입니다.

 

가장 먼저 풀었을 때는 머지소트를 시도했고, 그 다음에는 퀵소트를 시도했는데 둘다 메모리 초과가 떠서

 

검색해보던 와중 숫자의 최대치가 10000이라는 점을 이용해서 구하는 방법이 있어 그 방법으로 구현했습니다.

 

최대 숫자의 개수가 10000000개라서 이 방법으로 푸는게 맞는거 같습니다.

 

숫자가 나올때마다 카운트를 해서 마지막에 카운트 개수만큼 그 index를 출력하면 됩니다.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    cin >> n;
    
    int arr[10001] = {0,};
    
    for(int i=0; i<n; i++)
    {
        int a;
        cin >> a;
        arr[a]++;
    }
    
    for(int j=0; j<10001; j++)
        for(int k=0; k<arr[j]; k++)
            cout << j << '\n';
}