C언어 백준 10989번 수 정렬하기 3

문제 풀이

카운팅 정렬(계수 정렬)을 통해 풀어야 한다.

해당 정렬에 대한 설명은 아래에 있다.

계수 정렬(카운팅 정렬) 개념, 분석, 활용 (tistory.com)

 

처음 퀵 정렬인 qsort를 통해 문제를 풀어 보니 메모리 초과가 발생하였다. 메모리 제한은 8 MB인데, int arr[10000100] 등으로 선언을 하게 되면, 4Byte * 10000100 = 40000400 Byte = 40000KByte = 40 MB가 된다. 

소스코드

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define maxvalue 10001

int count[maxvalue]={};


int main(void)
{
	int N=0;
	int num=0;
	scanf("%d", &N);
	
	for (int i = 0; i<N; i++)
	{
		scanf("%d",&num);
		count[num]++;
	}
	
	for (int i = 1; i<maxvalue+1; i++)
	{
		if (count[i]!=0)
		{
			for (int j = 0; j<count[i]; j++)
			{
				printf("%d\n", i);
			}
		}
	}
	
	return 0;
}