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

풀이

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	ios::sync_with_stdio(false);	// cin, cout의 속도 증가
	int n,k;
	cin >> n >> k;
	int a[50000000];
	for (int i=0; i<n; i++) {		// 입력
		cin >> a[i];
	}
	k--;
	nth_element(a, a+k, a+n);		//정렬
	cout << a[k];
	return 0;
}

개념

nth_element(first, nth, last)는 CTL 중 하나로, 부분정렬을 해주는 함수이다.

first와 last까지의 요소 중 nth까지만 정렬한다.

---

풀이 

 

sort 함수를 다르게 사용하는 것 외에는 여타 정렬문제와 같다.

신경 써야할 부분은, 배열의 index는 0부터 시작하나 k의 index는 1부터 시작한다.

따라서 k--;를 통해 참조할 요소를 맞춘다. 

---

+a

사실 nth_element 연산을 하지않고 sort로 접근해도 해결되는 문제이다.

다만 속도측면에서 nth_element가 더 빠르다.

문제를 해결함에 있어 더욱 중요한 것은, ios::sync_with_stdio(false) 의 사용이다.

일반적인 cin, cout의 속도로는 시간초과가 발생한다.