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

백준 온라인 저지(BOJ) 10989번 수 정렬하기 3

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

10989번: 수 정렬하기 3

* 사용언어 : C언어, C++

 

1. 문제

10,000 이하의 자연수 N 개(최대 10,000,000개)를 정렬한 결과를 출력

 

2. 풀이

정렬 대상의 범위(숫자)가 적을 경우

속도가 빠른 Counting Sort 를 이용하여 풀었습니다.

 

처음에는 과거에 계수 정렬을 배웠던 내용을 되짚어보면서

count 배열, 입력 배열, 정렬 배열 총 3개를 선언하고 풀어봤는데 메모리 초과가 발생했습니다.

 

4 byte 짜리 int 를 10,000,000개 씩 2개나 선언했으니.. (약 80MB)

문제의 메모리 제한인 8MB를 훌쩍 넘은 것이었습니다.

 

2 Byte 인 short 로 배열을 선언하면 10,000 이하의 자연수를 표현할 수는 있지만

역시나 메모리 제한을 초과하게 됩니다.

 

그래서 count 만 저장하는 배열 하나만 남겨두었습니다.

 

 

입력 시에는 값을 굳이 저장하지 않고

count 배열의 해당 index 자리의 값만 1 증가시켰습니다.

 

입력이 끝나면 바로 출력을 하는데,

count 배열을 순회하면서 기록된 count(c[i])만큼 해당 숫자(i)를 출력하면 됩니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
10989_수 정렬하기 3
1152KB	2556ms
*/
#include <cstdio>

const int KLM = 10001;
int c[KLM], n, num;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &n);
	for (register int i = 0; i < n; ++i) {
		scanf("%d", &num);
		++c[num];
	}

	for (int i = 1; i < KLM; ++i) {
		for (int j = 0; j < c[i]; ++j) {
			printf("%d\n", i);
		}
	}
	return 0;
}

* 매우 많이 반복하여 접근하는 변수가 있다면, register 로 선언 시 약간 빠릅니다.