[BOJ] 10989. 수 정렬하기 3 - C++

https://www.acmicpc.net/problem/10989

 

#include <bits/stdc++.h>
using namespace std;

int arr[10001];
int main() {

	int n;
	cin >> n;

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

	for (int i = 0; i < 10001; i++) { 

		while (arr[i]--) {
			cout << i << '\n';
		}
	}
}

 

# Tip

이 정렬은 보통 STL sort나 O(N^2) 풀이를 할 때

N의 개수가 10,000,000여서 배열 선언을 하면 메모리가 너무 커서  메모리 초과가 일어난다.

이 수의 최대 자연수는 10000이니 이걸 이용해서 Counting Sort로 정렬을 하면 된다.