[ C++ ] #10989 수 정렬하기 3 ( 브론즈 I )

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

문제

---

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

출력

---

이는 원래 하던 merge sort로 하면 메모리 초과가 난다.

여기서 힌트로 봐야할 것은 숫자의 중복이 있다는 것과 입력되는 수는 10,000이하라는 것이다.

이 문제의 풀이는 10,000짜리 배열을 만들어서 각 숫자가 몇개 들어왔는지 세고 출력하는 것이다.

#include <iostream>
using namespace std;

int n;
int arr[10001];

int main(){

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin>>n;

    int num=0;

// 개수 세면서 입력받기
    for(int i=0;i<n;i++){ 

        cin>>num;
        arr[num]++;

    }

    for(int i=1;i<10001;i++){

        while(arr[i]--){ //개수만큼 출력하기 
            cout<<i<<"\\n";
        }

    }

}