움.. 이 문제는 퀵소트를 응용한 문제입니다.

퀵소트가 진행되는 방식을 생각해보면

1. 피벗을 정한다.

2. 피벗 보다 작은 수는 왼쪽으로 보내고 큰수는 오른쪽으로 보낸다.

3. 모두 이동시킨 뒤 피벗을 사이에 넣는다.(이때 피벗의 위치가 정해집니다.)

4. 피벗의 기준으로 왼쪽, 오른쪽 배열에 대하여 1번을 다시 수행한다.

만약 피벗이 정해졌을 때 그 위치가 k번째라면 더 정렬할 필요없겠죠?

그리고 k번째 위치만 찾으면 되므로 4번이 실행될 때 배열이 k 범위에 들어가지 않는다면 그 쪽은 수행안해도 되겠죠.

그래서 고려해야 할점은 아래와 같습니다.

1. 피벗을 선택하는 방법 ( 피벗을 잘못선택하면 퀵소트는 시간복잡도 O(N^2)을 가집니다.)

2. k번째 원소를 찾는데 필요없는 수행을 못하게 하기

아 nth_element() 써서 푸셔도됩니다. =ㅂ=;;

감사합니다..!