BOJ 백준 2751 : 수 정렬하기 2

시작하면서

이번 문제는 기수 정렬(radix sort) 카테고리 문제이다. 기수 정렬은 개념을 공부하고, 직접 구현해서 문제 풀이에 적용하려고 한다.

BOJ 2751 - 수 정렬하기 2

​

개념

기수 정렬(radix sort)은 낮은 자리 수부터 비교해 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다. 자릿수가 고정되어 있으니 안정성이 있다(이 때 데이터들 간의 상대적 순서는 보존되어야 함). 시간 복잡도는 O(dn)이다. (d는 가장 큰 데이터의 자리수)

예제를 통해서 알고리즘을 알아보자.

170, 45, 75, 90, 2, 24, 802, 66

위와 같은 데이터가 주어졌을 때, 첫 번째로 1의 자리 수만 보고 정렬을 진행한다.

170, 90, 2, 802, 24, 45, 75, 66

두 번째로 10의 자리 수만 보고 정렬을 진행한다.

2, 802, 24, 45, 66, 170, 75, 90

세 번째로 100의 자리 수만 보고 정렬을 진행한다.

2, 24, 45, 66, 75, 90, 170, 802

최대 자리 수까지 정렬을 완료했으므로 데이터 정렬이 완료되었다.

​

문제 이해

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

• N : 주어질 수의 개수

• 주어지는 수

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

​

문제 아이디어

이 문제는 시간 제한도 넉넉하고 메모리 제한도 넉넉해서 다른 정렬을 사용해도 상관없어 보인다. 하지만 지금은 기수 정렬을 공부하고 있으니 기수 정렬로 풀어보겠다.

​

해결

#include <iostream>
#include <queue>

using namespace std;

#define MAX_NUM (1000001)

void Input();
void RadixSort();
void PrintAnswer();

int N, maxValue;
queue<int> q[10];
int radixArray[MAX_NUM];

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

void Input()
{
	cin >> N;

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

void RadixSort()
{
	int radix = 1;

	// 음수를 양수로 만들어서 정렬한다.
	for (int i = 0; i < N; i++)
	{
		radixArray[i] += 1000000;

		if (radixArray[i] > maxValue)
		{
			maxValue = radixArray[i];
		}
	}
	
	// 기수 정렬 진행
	while ((maxValue / radix) > 0)
	{
		for (int i = 0; i < N; i++)
		{
			q[((radixArray[i] / radix) % 10)].push(radixArray[i]);
		}

		int index = 0;
		for (int i = 0; i < 10; i++)
		{
			while (!q[i].empty())
			{
				radixArray[index++] = q[i].front();
				q[i].pop();
			}
		}

		radix *= 10;
	}

	// 더해줬던 가중치를 다시 빼준다.
	for (int i = 0; i < N; i++)
	{
		radixArray[i] -= 1000000;
	}
}

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

문제를 풀면서 처음에 런타임 에러가 계속해서 나왔었다. 왜 그런지 문제를 자세히 읽어보니 [이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다.] 라는 구문이 있었다. 음수가 있었다…

그래서 기수 정렬을 하기 전에 최대값만큼 더해줬고, 기수 정렬을 끝낼때 최대값만큼 값을 빼주었다. 문제는 기수 정렬을 사용하면 바로 풀린다.

​

마치며

기수 정렬을 개념만 알고 구현해본 것은 처음이었다. 큐를 사용하면 쉬운데, 배열을 사용해서 하는 방법은 꽤나 어려워 보였다.

스터디를 진행할 때 다른 사람이 구현한 것을 참고해서 추후에 다시 해봐야겠다.