BOJ/10989

 

수 정렬하기 3

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>


int main(void) {

	int cnt;
	int arr[10001] = {0,};

	scanf("%d", &cnt);

	for (int i = 0; i < cnt; i++) {
		int stor;
		scanf("%d", &stor);
		arr[stor]++;
	}
	for (int i = 1; i < 10001; i++) {
		for (int j = 0; j < arr[i]; j++) {
			printf("%d\n", i);
		}
	}
	return 0;
}

 

10000000개의 수를 받기 위한 배열의 메모리를 단순 계산해보면 int(4byte)*10000000 = 40mb이다.

문제에서 주어진 메모리 제한은 8Mb이므로 메모리 초과로 인해 오류가 발생한다.

따라서  int형 100000000크기의 배열은 사용할 수 없다. 마찬가지로 char형도 1byte이므로 사용할 수 없다.

힌트는 입력되는 수가 10000이하의 자연수라는 것.

정수형 10000크기의 배열을 선언하여 모두 0으로 초기화시킨 후 1~10000의 수가 입력될 때마다 해당하는 자리에 1씩 더해준다.

출력시 2중 for문을 통해 해당 위치 (1~10000) 의 값만큼 만큼 배열 위치(1~10000)를 출력해주면 된다.