[BOJ] 10989. 수 정렬하기 3 (Counting Sort)

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

10989번: 수 정렬하기 3

처음에 Counting Sort로 풀라길래 정석적인 Counting Sort로 풀었는데 메모리 초과가 나서 게시판을 참고해서 줄이고 줄여서 풀었다.

원래 정렬 전 배열과 정렬 후 배열도 가지고 있었는데 N이 10,000,000 이하이기 때문에 10,000,000짜리 배열을 두 개나 가지고 있으니 메모리 차지를 많이 할 수 밖에 없었다.

그래서 입력 받은 수를 배열에 저장하지 않고 바로 numbersCnt 배열로 계수만 관리해주었다.

또, 이를 배열에 저장하면서 정렬할 필요없이 numbersCnt 배열의 index와 값을 이용해서 정렬된 결과를 쭉 출력해주었다.

#include <iostream>
#include <ios>
using namespace std;

int N, maxN;
int numbersCnt[10001];
void countingSort();
void print();

int main() {
	cin.tie(0); ios::sync_with_stdio(0);
	cin >> N;
	maxN = -2e9;
	for (int i = 0; i < N; i++) {
		int temp;
		cin >> temp;
		numbersCnt[temp]++;
		maxN = maxN < temp ? temp : maxN;
	}
	countingSort();
	return 0;
}

void countingSort() {
	for (int i = 1; i <= maxN; i++) {
		for (int j = 0; j < numbersCnt[i]; j++) {
			cout << i << "\n";
		}
	}
}