BaekJoon 10989 수 정렬하기 3

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

소스결과 1136 KB / 2444 ms

출처 Backjoon

언어 C

분류 정렬

 

설명

개수가 많아서 시간제한이 3초다, 근데 메모리는 고작 8 MB

배열을 전부 저장하게 되면 메모리는 견디지 못한다.

 

메모리가 넉넉했더라면 Quick Sort로 구현 해도 정답이 되겠지만 위 문제는 Quick Sort로 구현하는게 아니다.

 

중복되는 수가 존재하기 때문에 그 수의 개수만 알고 있으면 되고, 그 수를 순서대로 출력하는

Counting Sort를 구현하는 문제이다.

 

다른 Sorting과는 다르게 중복 되는 값이 존재하는 경우에 사용하는 Sorting 방법이다.

주 핵심은 중복되는 값의 개수를 저장하는 것이다.

 

알고리즘

1. 값을 입력 받으면서 값의 개수를 저장한다.

2. 1번 index 부터 값의 개수만큼 반복해 출력한다.

 

소스코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

short digits[10001];

int main()
{
	int n;

	scanf("%d", &n);

	for (int i = 0; i < n; i++)
	{
		short val;
		scanf("%hd", &val);
		digits[val]++;
	}

	// counting Sort
	for (int i = 1; i < 10001; i++)
	{
		for (int j = 0; j < digits[i]; j++)
			printf("%hd\n", i);
	}

	return 0;
}