[11004] K번째 수 (C++) / 2가지 풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k; cin >> n >> k;
	vector<int> A(n, 0);

	for (int i = 0; i < n; i++) cin >> A[i];

	sort(A.begin(), A.end());

	cout << A[k - 1];

	return 0;
}

 

1. sort 함수 사용 후 k번째 수, A[k-1] 출력

 

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

void quicksort(vector<int>& a, int start, int end);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k; cin >> n >> k;

	vector<int> a(n, 0);

	for (int i = 0; i < n; i++) cin >> a[i];

	quicksort(a, 0, n - 1);

	cout << a[k - 1];

	return 0;
}

void quicksort(vector<int>& a, int start, int end)
{
	if (start >= end) return;

	int pivot = start;
	int i = start + 1;
	int j = end;
	int temp;

	while (i <= j) {
		while (a[i] < a[pivot] && i <= end) i++;
		while (a[j] > a[pivot] && j >= start) j--;

		if (i >= j)
			break;

		temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	temp = a[j];
	a[j] = a[pivot];
	a[pivot] = temp;

	quicksort(a, start, j - 1);
	quicksort(a, j + 1, end);
}

 

1. 퀵 정렬 사용

2. pivot을 가장 앞 항으로 지정

3. i는 pivot의 다음 항, j는 마지막 항으로 지정

4. i가 pivot보다 작으면 i++, j가 pivot보다 크면 j--

5. i와 j가 멈추면 두 항을 swap

6. i와 j가 교차하는 지점에서 종료 후 j와 pivot을 swap

7. 재귀함수를 사용해 pivot을 중심으로 좌측과 우측의 vector에 대한 퀵 정렬 실행

8. start와 end가 일치하면 모든 퀵 정렬 종료