BOJ 15688 : 수 정렬하기 5 with In-Place Sort

알고리즘 문제 전체 링크

삼성 C형 전체 링크

 

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

 

참고 

- BOJ 2751 : 수 정렬하기 2 with 계수 정렬 (Counting Sort)

 

 

만약 배열 a의 크기가 매우 크지만 원소의 종류는 매우 적다면, count와 countSum의 배열의 크기는 작아진다.

따라서 이 경우에는 a의 원소의 종류만큼만 필요하게 되고

추가적인 메모리가 거의 없이 in-place 처럼 sorting이 가능하다.

 

이상적인 In Place 정렬은 다음과 같다.

함수 스택에서 약간의 메모리만 사용할 뿐 추가적인 메모리 없이 a[]에서 서로 교환한다.

void inPlaceSort(int a[], int size)
{
	int count[MAX + 10] = { 0 };
	int countSum[MAX + 10] = { 0 };

	for (int i = 0; i < size; i++) count[a[i]]++;
	for (int i = 0; i < MAX; i++) countSum[i] = count[i];
	for (int i = 0; i < MAX; i++) countSum[i + 1] += countSum[i];

	int ptr = 0;
	while (ptr < size)
	{
		int thisValue = a[ptr];
		int right = countSum[thisValue];

		if (ptr == right)
		{
			ptr += (count[thisValue]);
			continue;
		}

		int tmp = a[ptr];
		a[ptr] = a[right - 1];
		a[right - 1] = tmp;

		--countSum[thisValue];
	}
}

 

이 문제는 원소의 종류가 매우 크기 때문에 count / countSum을 바깥에 선언하였다.

#include <stdio.h>

#define MAX   (20000)
#define MINUS (10001)

int N;
int a[MAX + 10];
int count[MAX + 10];
int countSum[MAX + 10];

void inPlaceSort(int a[], int size)
{
	for (int i = 0; i < MAX; i++) countSum[i] = count[i];
	for (int i = 0; i < MAX; i++) countSum[i + 1] += countSum[i];

	int ptr = 0;
	while (ptr < size)
	{
		int thisValue = a[ptr];
		int right = countSum[thisValue];

		if (ptr == right)
		{
			ptr += (count[thisValue]);
			continue;
		}

		int tmp = a[ptr];
		a[ptr] = a[right - 1];
		a[right - 1] = tmp;

		--countSum[thisValue];
	}
}

int main(void)
{
	scanf("%d", &N);

	for (int i = 0; i < N; i++)
	{
		scanf("%d", &a[i]);
		a[i] += MINUS;
		count[a[i]]++;
	}

	inPlaceSort(a, N);

	for (int i = 0; i < N; i++) printf("%d\n", a[i] - MINUS);

	return 0;
}