[백준/BOJ/C++] 10989번 수 정렬하기 3 - 정렬

10989번: 수 정렬하기 3

1. 문제

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

---

2. 입력

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

---

3. 출력

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

---

4. 풀이

이 문제에서 메모리제한이 8MB이기 때문에 단순히 입력된 N으로 크기가 N인 배열을 만들어서 풀면 메모리 초과가 나오게 된다. 따라서, 수의 범위가 10,000까지이기 때문에 계수정렬 방식으로 정렬을 해준다.

계수정렬은 입력된 수에 해당하는 배열의 인덱스에 값을 더해주는 방식이다.

예를 들어, 숫자 5가 입력되면 arr[5]의 값에 +1을 해준다. 이렇게 모두 입력받은 다음 출력할때는 해당 인덱스의 값만큼 출력을 해준다.

** 추가로 해당문제에서 c++을 사용할때 cin과 cout으로 인해 시간초과가 걸리게 된다. 

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

그래서 상단 코드를 추가해준다.
C표준 stream과 C++표준 stream의 동기화를 끊는 역할을 하는데, 동기화를 끊으면 C++ stream은 독립적인 버퍼를 갖게되며, 실행 속도가 향상된다.

 

---

5. 소스코드

#include <iostream>
using namespace std;
int main(){
    ios_base::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 tmp;
        cin>>tmp;
        arr[tmp]++;
    }
    for(int i = 1; i < 10001; i++){
        for(int j = 0; j < arr[i]; j++){
            cout<<i<<"\n";
        }
    }
    return 0;
}