[코딩테스트] [BOJ24090] 알고리즘 수업 - 퀵 정렬 1

문제

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

---

풀이

0. 의사코드를 C++ 코드로 작성한다

1. 맨 끝 원소를 pivot으로 잡고, -1부터 index를 시작해서 작은 값을 왼쪽 정렬, 큰 값을 오른쪽 정렬한다
   1-1. 이때, n-1보다 작을때까지 index를 증가시켜 반복문이 끝나도 pivot이 유지되도록 보장한다
   1-2. 반복문이 끝나면, pivot을 기준으로 작은 값은 index보다 왼쪽 큰 값은 오른쪽에 정렬되었다
   1-3. 따라서 index + 1에 있는 원소와 pivot 원소를 바꿔준다

2. swap할 때 마다 count 증가하고, 현재 값을 pair에 저장한다

---

코드

#include <iostream>
#include <vector>
using namespace std;

int swapCount = 0;
int targetCount = 0;
pair<int, int> pairTemp;

void swap(int& left, int& right)
{
	swapCount++;

	int temp = left;
	left = right;
	right = temp;

	if (swapCount == targetCount)
	{
		pairTemp.first = left;
		pairTemp.second = right;
	}
}

int partition(vector<int>& arr, int start, int end)
{
	// index : pivot보다 작거나 같은 값들의 마지막 위치
	int pivotValue = arr[end];
	int index = start - 1;
	for (int j = start; j < end; j++)
	{
		if (arr[j] <= pivotValue)
		{
			index++;
			swap(arr[index], arr[j]);
		}
	}

	// index + 1 요소값으로 pivot 변경
	if (index + 1 != end)
	{
		swap(arr[index + 1], arr[end]);
	}

	return index + 1;
}

void quick_sort(vector<int>& arr, int start, int end)
{
	if (start < end)
	{
		int pivot = partition(arr, start, end);
		quick_sort(arr, start, pivot - 1);
		quick_sort(arr, pivot + 1, end);
	}
}

int main()
{
	int n = 0;
	cin >> n >> targetCount;

	vector<int> field(n);
	for (int i = 0; i < n; i++)
	{
		cin >> field[i];
	}

	quick_sort(field, 0, n - 1);

	if (swapCount < targetCount)
	{
		cout << -1;
	}
	else
	{
		cout << pairTemp.first << ' ' << pairTemp.second;
	}

	return 0;
}