[C++] BOJ (백준) 10989 : 수 정렬하기 3

문제

10989번: 수 정렬하기 3 (acmicpc.net)

10989번: 수 정렬하기 3

코드 (Counting Sort)

#include <iostream>

#define MAX_NUM 10000

using namespace std;

int arr[MAX_NUM + 1];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  while (n--) {
    int num;
    cin >> num;
    arr[num]++;
  }

  for (int i = 1; i <= MAX_NUM; i++) {
    for (int j = 0; j < arr[i]; j++) {
      cout << i << '\n';
    }
  }
  return 0;
}

설명

10,000,000개의 int 데이터를 저장하려면 약 40MB가 필요한데,
메모리 제한이 8MB이므로 데이터 자체를 저장할 수는 없다.
반면 입력받은 수의 최댓값은 10,000에 불과하므로 입력받은 값에 해당하는 배열의 값을 저장하면 된다.