[C++] 백준 10989번: counting sort 사용해보기!

📎 백준 10989번 풀러 가기

10989번: 수 정렬하기 3

문제

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

입력

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

출력

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

---

counting sort는 정렬 알고리즘 중 하나로, 

메모리를 매우매우! 많이 잡아먹지만 시간은 O(n+k)로, 굉장히 빠른 알고리즘이다.

 

지난 학기에 알고리즘 시간에 배우기만 했는데, 이번 문제를 통해 직접 구현을 해보았다.

확실히 빠르기는 한데, 메모리를 정말정말 많이 잡아 먹는 것 같다.

장단점에 따라 더 적절한 알고리즘을 판단하는 능력을 많이 길러야 함을 느꼈다.

 

그리고! 이 문제는 counting sort를 구현하는 것에는 그다지 애를 먹지 않았으나,

자꾸 시간 초과가 나서 애를 먹었다.

 

그 이유가 무엇일까 고민을 해보았는데,

cin, cout의 시간을 빠르게 하기 위하여 추가한 코드 중에서

 

  ios::sync_with_stdio(false);

  cin.tie(NULL);

  cout.tie(NULL);

 

이 부분에서 내가 false를 빼먹고 계속 채점을 시도하고 있었다.

false를 추가하니 당연히 성공.

앞으로 절대, 네버! false를 빼먹는 일이 없도록 해야겠다.

---

아래는 내가 구현한 코드👇

#include <iostream>
using namespace std;

int box[10001];

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

    int n; 
    cin >> n;

    int temp = 0;   
    for (int i = 0; i < n; i++) {
        cin >> temp;
        box[temp]++;
    }

    for (int i = 1; i <= 10000; i++) {
        while (box[i]) {
            cout << i << '\n';
            box[i]--;
        }
    }
    return 0;
}