百準10999/数ソート3


質問する




に答える


今回のソート問題の入力Nの範囲は1000000である.
したがって、これらの入力値をすべて保存すると、当然メモリを超えます.
また,3秒の時間制限と8 MBのメモリ制限を考慮すると,デュアルforゲートで問題を解決するのはよくない.
△考えずに解いてしまったので、力を入れてしまった.
だから思い切って考えを変えて、再び近づきます.
並べ替えが必要な数値範囲が1〜10000であることを考慮して,10000の大きさの配列を作成し,数で解いた.

コード#コード#

#include <iostream>

using namespace std;

int n = 0;
// 숫자 개수를 저장하는 배열
int cnt[10001] = { 0 };

int main() {
	// cin, cout의 속도를 높여준다.
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int num = 0;
	cin >> n;

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

	for (int i = 1; i < 10001; i++) {
		while (cnt[i] != 0) {
			cout << i << '\n';
			cnt[i]--;
		}
	}

	return 0;
}
関連項目:https://www.acmicpc.net/problem/10989