[백준] #10989: 수 정렬하기 3

문제

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

입력

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

출력

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

예제 입력 1 

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1 

1
1
2
2
3
3
4
5
5
7

 

코드

#include <iostream>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int T;
    cin >> T;

    int arr[10001] = { 0 };

    // 숫자 개수 카운트
    for (int i = 0; i < T; i++) {
        int a;
        cin >> a;
        arr[a] += 1;
    }

    // 각 숫자를 개수만큼 출력해주기
    for (int i = 1; i <= 10000; i++)
        for (int j = 0; j < arr[i]; j++)
            cout << i << "\n";
}

---

이 문제는 문제에 메모리가 한정되어 있기 때문에 메모리 초과가 일어나지 않기 위해서는 숫자 개수를 카운트해서 풀어줘야한다
즉, 계수정렬을 이용하면 된다

https://12yeonii.tistory.com/59

[이취코] ch06-4. 계수 정렬 (Count Sort)

 

먼저 배열에 들어갈 숫자의 개수를 입력받고, 배열에 들어갈 수를 그 갯수만큼 반복해서 입력할때
들어가는 숫자를 arr 라는 배열의 인덱스 값으로 보고 그 배열에 해당하는 값을 +1 해준다음 출력만 하면 되는 문제였다

 

**

ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

이 세 코드는 실행 속도를 빠르게 하기 위해 작성해주었다