[C++] 백준 10989번: 수 정렬하기 3

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

10989번: 수 정렬하기 3

수의 개수가 1천만인데 반해 수의 범위 구간은 [1, 10000]이다. 메모리 제한이 8MB라서 1천만개의 숫자를 모두 저장하면 메모리 초과가 발생한다. 10000까지 표현 가능한 데이터 타입 중 가장 작은 바이트 단위를 가진 short(2바이트)를 이용해도 19MB이다. 그래서 찾아보니 Counting Sort를 이용해야 한다고 한다.

https://bowbowbow.tistory.com/8

Counting Sort : 계수 정렬

크기가 1만인 int 배열을 선언하고 각 인덱스 + 1의 숫자가 들어오면 해당 인덱스의 값을 1씩 더해주었다. 입력을 모두 받은 후에는 처음부터 저장된 숫자가 0이 될 때까지 저장된 수를 감소시키며 해당 인덱스 + 1의 값을 출력해줌으로써 문제를 해결했다. Counting Sort의 본래 의도대로라면 불필요한 순회를 피하기 위해 누적 개수 합을 저장해야 한다고 하지만 1만 밖에 되지 않는 크기라서 그냥 이대로 해서 AC를 받았다.

#include <bits/stdc++.h>

using namespace std;

#define TC(T) int T; cin >> T; while(T--)
#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define ERR 1e-13
#define EL "\n"
#define VI vector<int>
#define VVI vector<VI>
#define VVVI vector<VVI>

int cnt[10'000];

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

	int N;
	cin >> N;

	FOR(i, N) {
		int num;
		cin >> num;
		cnt[num - 1]++;
	}

	FOR(i, 10'000) {
		while (cnt[i]) {
			cout << i + 1 << ' ';
			cnt[i]--;
		}
	}
	cout << EL;

	return 0;
}