[C++] 백준 11004번 - K번째 수

---

0. 문제

 

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

 

1. 아이디어

 

1) 단순히 sorting 한 후에 K번재 index를 참조하면 시간초과가 난다..

 

2) 따라서 Quick Selection 이라는 방법을 새로 사용해야 했다! (nth_element)

 

2. 소스코드

 

#include <iostream>
#include <algorithm>
#include <vector>
std::vector<int> v;
int main()
{
	std::ios_base::sync_with_stdio(0);
	std::cin.tie(0);
	int N, K;
	std::cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		int input;
		std::cin >> input;
		v.push_back(input);
	}
	std::nth_element(v.begin(), v.begin() + K-1, v.end());
	std::cout << v[K-1];
}

 

3. 결과

 

 

4. 피드백

 

• 조금 알겠다 싶으면 자꾸 새로운게 나오는구나 ~~

---