[백준]10989번 수 정렬하기 3

문제

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

입력

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

출력

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

#include <bits/stdc++.h>
using namespace std;  
int counts[10001];
int main(void) {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int num;
    cin >> num;
    for (int i = 1;i <=num;i++)  {
      int temp;
      cin >> temp;
      counts[temp]++;
    }

    for(int i =1; i<=10001;i++) {
      counts[i] += counts[i-1];
    }

    for(int i = 1; i<=10001;) {
      if (counts[i-1] < counts[i]) {
          cout << i <<  "\n";
          counts[i-1]++;
          continue;
      }
      i++;
    }

}

이 문제의 답의 핵심은 총 3가지다.

첫 번째, 카운팅 정렬을 사용했다.

    - 카운팅 정렬은 일반 정렬과 달리 배열의 index를 가지고 정렬하는 방법이다.

   어떻게 index를 가지고 정렬이 가능한 이유는 바로 누적을 시켰기 때문이다.

   누적을 시켰기때문에 숫자가 점진적으로 증가되는 것을 확인 할 수 있다. 

   예를 들어 처음 배열이

   0 2 2 2 1 2 0 1 이라고 하면

   0 2 4 6 7 9 9 10 이 된다. 그러면 자연스럽게 0번째는 1번째보다 2만큼 작기 때문에 우리는 1이 2개가 존재한다는 것을 유추 할 수 있다. 또한, 마지막에서 왼쪽 1번째는 그 전꺼랑 비교 했을때, 0개라는 걸 보았을때, 이 숫자는 존재하지 않는 걸로 확인된다. 

  

   인덱스로 값을 정렬을 시키다니... 신기할 따름이다. 잘 모르지만 범위가 기하급수적인 경우에는 사용하기가 어려울 것 같다. 왜냐하면 그 값들을 전부 저장시켜야하는데 만만치 않다. 또한 음수는 되지도 않는다. 

이런 단점이 있기는 하지만 범위가 좁은 경우에는 사용하는것도 나쁘지 않을 것 같다.

 

두 번째, ios_base:: ...를 사용했다.

  = > 시간 초과가 발생한다.

세 번째, 반복문 최대 크기를 10001로 잡았다.

  = > 런타임 에러가 발생한다.