[백준 2750번][C++] 수 정렬하기

<문제 소개>

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <unordered_map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

void PositiveCountingSort(vector<int>& v, int maxVal)
{
	vector<int> count(maxVal + 1); // 각 데이터 별 개수를 저장할 벡터

	for (int i = 0; i < v.size(); i++)
	{
		count[v[i]]++; // 각 데이터 별로 갯수를 셈
	}

	// 0부터 오름차순으로 정렬할 것이므로 0번은 구했던 값 그대로이기 때문에 1부터 시작
	for (int j = 1; j < count.size(); j++)
	{
		// 자신의 값에 이전의 원소를 더해줌
		count[j] += count[j - 1];
	}

	vector<int> result(v.size()); // 정렬될 숫자들을 담을 벡터

	for (int k = 0; k < v.size(); k++)
	{
		int insertVal = v[k]; // 넣을 값
		int insertIndex = --count[insertVal]; // 넣을 인덱스 번호

		result[insertIndex] = insertVal;
	}

	v = result;
}

void NegativeCountingSort(vector<int>& v, int minVal)
{
	vector<int> count(-minVal + 1); // 각 데이터 별 개수를 저장할 벡터

	for (int i = 0; i < v.size(); i++)
	{
		// 각 데이터 별로 갯를 셈 -> 음수이므로 -1을 곱해줌
		count[v[i] * -1]++; 
	}

	// 음수를 오름차순으로 정렬해야함
	// 인덱스는 양수이므로 반대로 누적합을 구함
	// 인덱스의 시작이 count.size() - 1인데 해당 원소의 누적합은 그대로이므로 구할 필요 없음
	// count.size() - 2부터 자신의 앞의 원소를 더해주며 누적합을 구함
	for (int j = count.size() - 2; j >= 1; j--)
	{
		// 자신의 값에 앞의 원소를 더해줌
		count[j] += count[j + 1];
	}

	vector<int> result(v.size()); // 정렬될 숫자들을 담을 벡터

	for (int k = 0; k < v.size(); k++)
	{
		int insertVal = v[k]; // 넣을 값
		int insertIndex = --count[insertVal * -1]; // 넣을 인덱스 번호

		result[insertIndex] = insertVal;
	}

	v = result;
}


int main()
{
	// 쓰레드 환경이 아닐때 버퍼를 분리하여 처리속도를 빠르게 해줌
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	vector<int> v; // 최종 결과(음수+양수)

	vector<int> positive; // 양수
	vector<int> negative; // 음수

	// 벡터의 크기를 정하기 위함
	int maxVal = 0; // 최댓값
	int minVal = 0; // 최솟값
	
	// 원소 입력
	while (N > 0)
	{
		int x;
		cin >> x;

		if (x < 0)
		{
			// 음수
			negative.push_back(x);
			minVal = minVal > x ? x : minVal;
		}
		else
		{
			// 양수(0 포함)
			positive.push_back(x);
			maxVal = maxVal < x ? x : maxVal;
		}

		N--;
	}

	// 9. 카운팅 정렬
	// - 값의 갯수에 따라 해당 위치를 설정해주는 방식
	// 1. 각 데이터 별 갯수를 파악
	// 2. 누적합을 구하는 방식으로 정렬하고 싶은 순서에 따라 계산을 해준다.
	// ex) 오름차순 -> a[0] = a[0], a[1] = a[0] + a[1], a[2] = a[0] + a[1] + a[2} ...
	// 3. 새로운 배열에 해당 값이 가지는 누적합의 결과에 따라 위치를 넣어준다.
	// 4. 인덱스는 0부터 시작이므로 누적합 결과 - 1 에 해당되는 위치에 값을 넣는다.
	// 5. 중복되는 값이 있을 수 있으므로 하나를 넣을 때마다 누적합 결과를 1씩 빼준다.s
	// ex) a[3] = 7 -> 3을 정렬된 배열 (7-1)번째 인덱스에 넣고 a[3] = 6으로 변경
	PositiveCountingSort(positive, maxVal);
	NegativeCountingSort(negative, minVal);

	// 음수와 양수를 합쳐서 v에 저장
	negative.insert(negative.end(), positive.begin(), positive.end());
	v = negative;

	// 원소 출력
	for (int i = 0; i < v.size(); i++)
	{
		cout << v[i] << endl;
	}

	return 0;
}

<풀이과정>

1. 양수와 음수를 각각 나눠서 풀어야 하므로 각각의 벡터를 선언해 준다.

2. 또한 양수에서는 최댓값이, 음수에서는 최솟값이 이후 생성할 벡터의 크기를 결정하므로 최댓값과 최솟값 변수도 선언해 준다.

3. 입력을 받으면서 입력 값이 0보다 작으면 음수 벡터 negative에 넣어주면서 최솟값 minVal 인지 확인해준다.

4. 마찬가지로 입력 값이 양수일때는 해당 값을 positive 벡터에 넣고, maxVal 인지를 확인해준다.

5. PositiveCountingSort()

5-1. 양수를 정렬해 줄 것이므로 앞서 구한 positive 벡터와 maxVal를 인자로 받아온다.

5-2. 받아온 maxVal만큼 데이터 별 개수를 저장하고 이후에는 누적합을 이용해 넣을 위치를 찾을 벡터 count를 선언하고, 인덱스는 maxVal+1의 크기로 초기화하여 maxVal에 해당되는 인덱스도 생성되게 한다.

5-3. v의 원소들을 돌면서 count에 해당 원소번째 인덱스의 값이 나올때마다 1씩 증가시켜주면서 데이터 별 개수를 센다.

5-4. count에 저장된 데이터 별 개수를 이용해 1번 인덱스부터 차례로 이전 인덱스에 해당 값을 더해주는 작업을 한다. 이 작업을 하면 해당 데이터가 위치할 마지막 번호가 저장된다.

(이때, 0번의 누적합은 그대로 이므로 구할 필요가 없어서 1번부터 시작)

5-5. 정렬될 숫자들을 담을 벡터 result를 선언하고 크기를 v의 크기만큼 초기화 시킨다.

5-6. v의 원소들을 돌면서, result에 원소들을 자리게 맞게 넣어 정렬시킨다.(result[insertIndex] = insertVal;)

5-7. insertVal에는 result에 실제로 넣을 값인 v의 원소를 차례로 넣고, insertIndex에는count[insertVal]의 값을 넣어준다.

(이때, 인덱스 값은 0부터 시작이므로 count[insert]의 이전 값을 넣어주어야 하고, 넣어준 뒤 중복 값을 넣어주기 위해 해당 값을 실제로 1씩 감소시켜주어야 하므로, 감소연산자 '--'를 전증가를 이용해 넣어주어 insertIndex에도 이전 값을 넣으면서 동시에 실제 값도 1씩 감소시켜준다. -> inserIndex = --count[insertIndex])

5-8. 정렬된 result 벡터를 v에 대입한다.

6. NegativeCountingSort()

6-1. 음수를 정렬할 것이므로 앞서 구한 negative 벡터와 minVal를 인자로 받아온다.

6-2. 양수를 정렬할 때와 마찬가지로 count 벡터를 -minVal+1 크기로 선언한다.(minVal는 음수이므로 -1을 곱해준다.)

6-3. 음수를 오름차순으로 정렬해야 하는데, 음수는 절댓값이 작은 수가 큰 수이므로 양수와는 반대로 누적합을 구한다.

6-4. (count의 크기 - 1)이 마지막 인덱스 번호인데, 해당 원소의 누적합은 따로 구할 필요가 없으므로 (count의 크기 -2)부터 1까지 반대순서로 돌면서 자신의 앞순서의 원소를 더하여 누적합을 구한다.

6-5. result 벡터를 선언하고, 양수와 마찬가지로 insertVal와 insertIndex를 구해서 result 벡터를 구하는데, insertindex를 구할때, insertVal의 값이 음수이므로 count벡터에 -1을 곱한 인덱스번호에 접근하여 구해준다.

6-6. 정렬된 result 벡터를 v에 대입해준다.

7. 위의 과정이 끝나면 음수는 음수대로 정렬되어 negative 벡터에 들어가 있고, 양수는 양수끼리 정렬되어 positive 벡터에 들어가 있는 상태가 되는데, 최종 결과는 둘을 합친 벡터이어야 하므로 벡터에 내장된 insert() 함수를 이용해 negative의 마지막 자리에 positive벡터의 처음부터 끝까지를 삽입한다.

8. 이후 negative 벡터를 최종 결과를 저장할 벡터 v에 대입시키고 v를 하나씩 출력한다.

cf) 적으면서 생각난 건데 굳이 v를 선언하지 않고 그냥 negative의 원소를 출력하거나, 아니면 아예 negative원소를 출력하고 positive 원소를 이어서 출력하는 방법도 있겠다.

-> 그래서 둘 다 해봤는데 왜 인지는 모르겠는데 처음 풀었던 방식이 가장 빠른 결과가 나왔다.(뭐지..?)

<코멘트>

드디어 마지막 아홉번째 방법인 카운팅 정렬로 풀어보았다!

양수 음수 나눠서 푸는 것과 벡터의 크기를 미리 정해줘야 하는 것이 난관이었다.

- 카운팅 정렬 -

장점

- 비교를 하지 않고 정렬하는 방법으로 시간복잡도가 O(N)이 되어 매우 빠른 정렬법이다.

단점

- 숫자의 갯수를 저장해야될 공간과 결과를 저장해야될 공간 등의 추가적인 메모리 공간이 필요하다.

- 하나의 값 때문에 메모리의 낭비를 많이 할 수 있음