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

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

10989번: 수 정렬하기 3

처음에는 아무 생각 없이 정렬해서 풀다가 틀려서 봤더니 메모리 제한이 8MB였다. 구글링을 해보니 수를 모두 입력받아서 저장하면 메모리를 초과하게 되니 입력받은 숫자의 개수를 세는 식으로 접근해야 한다고 한다. 즉 [5, 2, 3, 1, 4, 2, 3]을 입력받았을 때 각 숫자를 입력받아 저장하는 것이 아니라 0으로 초기화 된 배열의 n번째 인덱스를 추가해주는 식으로 풀어 주어야 한다. 정답 코드는 아래와 같다.

#include <iostream>
using namespace std;

int arr[10001] = { 0 };

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

	int t;
	cin >> t;
	for (int i = 0; i < t; i++) {
		int k;
		cin >> k;
		arr[k]++;
	}
	for (int i = 0; i < 10001; i++) {
		for (int k = 0; k < arr[i]; k++) {
			cout << i << "\n";
		}
	}
}