[BOJ]11004 - 퀵소트/퀵셀렉션/머지소트

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

11004번: K번째 수

 

C++에 sort를 사용하면 된다.

 

입력이 5,000,000이니 O(nlogn)이면 가능하다고 판단됨.

 

다만, cout / cin 대신 scanf와 printf 를 사용해야함.

 

입출력 속도가 차이가 많이 나기에 이것만 바꿔도 시간초과냐 통과냐가 갈림.

 

 

해당 문제는 Quick Sort 대신 Quick Selection Sort를 사용하면 O(n)에 해결할 수 있다고함

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;


//int arr[5000000];
vector<int> v;

int main() {

	int N, k;
	cin >> N >> k;

	for (int i = 0; i < N; i++) {
		int tmp;
		scanf("%d", &tmp);
		v.push_back(tmp);
	}

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

	printf("%d", v[k - 1]);


	return 0;
}