BOJ 백준 2751 : 수 정렬하기 2

시작하면서

이번 문제는 바로 전에 푼 문제랑 동일한 문제를 푼다. 하지만 방법을 바꿔서 버킷 정렬(Bucket Sort)을 구현해서 풀려고 한다.

BOJ 2751 - 수 정렬하기 2

​

개념

버킷 정렬(Bucket Sort)는 수많은 버킷에 배열 요소들을 분산시킴으로써 동작하는 정렬 알고리즘이다. 각 버킷은 그 뒤로 개별 정렬되는데, 이는 다른 정렬 알고리즘을 사용하거나 버킷 정렬 알고리즘을 반복 적용시켜 수행한다.

버킷 정렬은 분석 대상 데이터의 분포 특성을 활용해 계산복잡성을 O(n) 수준으로 개선시키려는 것을 목적으로 한다. 버킷 정렬은 데이터가 특정 범위 내에 확률적으로 균등하게 분포한다고 가정할 수 있을 때 사용하면 좋다.

버킷 정렬은 다음과 같이 이루어진다. 그림 출처 : 위키백과

1. 처음에 비어있는 버킷들의 배열을 배치한다.
2. 분산 : 원래의 배열을 살펴보고 각 객체를 버킷에 담는다.
3. 비어있지 않은 각 버킷을 정렬한다.
4. 수집 : 순서대로 버킷을 방문해 모든 요소를 원래의 배열에 위치시켜 놓는다.

함들 안에 요소들이 산재되어 있다.

이후 각 함 안에 요소들이 정렬된다.

버킷 정렬은 시간 복잡도가 O(n)이다.

이때 사용하는 버킷 수에 비례해서 공간복잡도가 늘어나서 공간 복잡도는 O(nk)이다. (k : 버킷 수)

​

문제 이해

문제를 읽어보자. 먼저 이 문제에서 나오는 변수는 총 2가지이다.

• N : 주어질 수의 개수

• 주어지는 수

  이 변수를 가지고 답을 출력해야 한다.

​

문제 아이디어

버킷 정렬을 공부하고 있으니 버킷 정렬로 풀어보겠다.

​

해결

#include <iostream>
#include <queue>

using namespace std;

#define INPUT_SIZE      (1000001)
#define BUCKET_RANGE    (2000)
#define BUCKET_SIZE		(1001)

void Input();
void BucketSort();
void PrintAnswer();

int N;
int inputArray[INPUT_SIZE];
priority_queue<int, vector<int>, greater<int>> bucketQueue[BUCKET_SIZE];

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	Input();
	BucketSort();
	PrintAnswer();
}

void Input()
{
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> inputArray[i];
	}
}

void BucketSort()
{
	for (int i = 0; i < N; i++)
	{
		int index = 0;

		// 음수를 양수로 만들기 위해 100만을 더해준다.
		inputArray[i] += 1000000;	
		index = inputArray[i] / BUCKET_RANGE;
		bucketQueue[index].push(inputArray[i]);
	}

	int bucketIndex = 0, arrayIndex = 0;
	while (bucketIndex < BUCKET_SIZE && arrayIndex < INPUT_SIZE)
	{
		if (bucketQueue[bucketIndex].empty() == true)
		{
			bucketIndex++;
			continue;
		}

		// 더해준 100만을 빼준다
		inputArray[arrayIndex] = bucketQueue[bucketIndex].top() - 1000000;
		
		bucketQueue[bucketIndex].pop();
		arrayIndex++;
	}
}

void PrintAnswer()
{
	for (int i = 0; i < N; i++)
	{
		cout << inputArray[i]<< "\n";
	}
}

이전에 푼 문제랑 동일하기 때문에 딱히 어려운 부분은 없었다.

문제를 풀면서 버킷 정렬에 관해 느낀건

1. 버킷 범위를 적절히 정해야 메모리-수행 시간을 모두 잡을 수 있다.
2. 버킷 정렬을 사용하려면 버킷을 나눈 후에 정렬을 한 번 더 해야하는데, 다른 조건이 없다면 힙을 사용하는 우선순위 큐를 사용하면 간편하다.

​

마치며

버킷 정렬은 이전 기수/계수 정렬을 공부했더니 비슷한 맥락이어서 그런가 이해가 빠르게 되었다. 또한, 메모리만 충분히 주어진다면 수행 시간이 빠르기 때문에 충분히 자주 사용할 수 있을듯하다.

기회가 있다면 실전에서도 잘 사용해보자.