백준 10989 / 수 정렬하기 3

문제

풀이

이번 정렬문제는 입력하는 N의 범위가 무려 10,000,000이다.
따라서 이 입력값을 전부 저장하면 당연히 메모리가 초과될것이다.
그리고 시간제한 3초와 메모리제한 8MB를 고려해도 이중for문으로 푸는것은 아무래도 좋지 않은 선택이었다.
(고려 안 하고 풀었다가 엄청 해멨다.)

그래서 아예 생각을 전환해서 다시 접근해봤다.
정렬해야 하는 수의 범위가 1 ~ 10,000인 점을 고려하여 크기가 10,000인 배열을 만들어서 해당 숫자의 갯수를 세는 방식으로 풀어봤다.

코드

#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