[BOJ] 10989 수 정렬하기 3

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

Note

개수가 많아서 시간제한이 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;
}

2019-01-12 12:30:00에 Tistory에서 작성되었습니다.