11004번 (silver 5)

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

 

stl에서 sort를 하면 간단하지만, 직접 구현해서 풀어보겠다.

 

#include <iostream>
#include <vector>

using namespace std;

template <typename T>
void quickSort(vector<T>&, int s, int e);
template <typename T>
void swap(vector<T>&, int i, int j);
template <typename T>
int partition(vector<T>&, int i, int j);

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	int N, num;
	cin >> N >> num;
	vector<int> arr(N, 0);
	for (int i = 0; i < N; ++i) {
		cin >> arr[i];
	}

	quickSort<int>(arr, 0, arr.size() - 1);
	
	cout << arr[num - 1];
	return 0;
}

template <typename T>
void quickSort(vector<T>& arr, int s, int e) {
	if (s < e) {
		int pivot = partition(arr, s, e);
		quickSort(arr, s, pivot - 1);
		quickSort(arr, pivot + 1, e);
	}


}
template <typename T>
void swap(vector<T>& arr, int i, int j) {
	T temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
}

template <typename T>
int partition(vector<T>& arr, int s, int e) {
	int m = (s + e) / 2;
	swap(arr, s, m);

	int i = s + 1, j = e;
	const int pivot = arr[s];
	while (i <= j) {
		while (i <= e && arr[i] < pivot) {
			i++;
		}
		while (j >= s + 1 && arr[j] > pivot) {
			j--;
		}

		if (i < j) {
			swap(arr, i++, j--);
		}
		else
			break;
	}

	arr[s] = arr[j];
	arr[j] = pivot;

	return j;
}

 

while (i <= e && arr[i] < pivot) {
i++;
}
while (j >= s + 1 && arr[j] > pivot) {
j--;
} 이 부분에서 i <= e && arr[i] < pivot가 arr[i] < pivot && i <= e처럼 순서가 바뀌면 error가 발생할 수 있는데,

컴파일러마다 다르겠지만, 조건문에서 and로 연결된 논리식을 평가할 때, 첫 번째 조건(A)이 False라면 나머지 조건(B)을 평가하지 않고 바로 False를 반환하는 최적화 기법인 "단축 평가(short-circuit evaluation)"가 적용되기 때문이다.