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

📌 백준 10989 수 정렬하기 3
https://www.acmicpc.net/problem/10989

이 문제는 주목해야할 부분이 있다. 바로 이것

간단하게 생각해보면
N개의 원소를 가지는 배열을 만들어 주고
배열에 원소를 입력 받아서 sort() 해준 후 출력하면 된다.
근데 이렇게 하면 메모리가 초과가 난다.
N은 1부터 1000만까지다.
int 배열이니까 4byte x 1000만 = 40MB다.
8MB? 어림도 없다.

그럼 어떻게 해야할까
문제에서 제한을 준게 또 하나 있다. N개의 수를 입력받을 때 입력받는 수는 10000보다 작다는 것이다.
크기가 10001인 배열을 만들고, 입력 값이 idx와 동일하면 value로 개수를 +1 해서 넣어주는 것이다.
풀이는 아래와 같다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

	int N, idx;
	int cnt[10001] = {};
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> idx;
		cnt[idx] += 1;
	}

	for (int i = 1; i <= 10000; i++)
	{
		for (int j = 1; j <= cnt[i]; j++)
		{
			cout << i << "\n";
		}
	}
}