k번째 큰 수 찾기

문제

N개의 자연수가 주어질 때, 이 자연수들 중에서 k번째로 큰 수를 찾는 프로그램을 작성하시오. 만약 k=1 이라면, 가장 큰 수를 찾으면 된다.

 

입력

첫 번째 줄에 자연수 N, k가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ k ≤ 10) 두 번째 줄에 N개의 자연수가 주어진다.  

 

출력

첫 번째 줄에 k번째 수를 출력한다.

 

예제 입력

10 3

1 5 2 3 8 4 7 3 2 10

 

예제 출력

7

 

예제 입력

5 4

5 5 1 2 3

 

예제 출력

2

 

------------------------------------------------------------------------------------------------------------------------------

 

문제의 조건을 잘 읽어보니 k는 1부터 10까지의 수이다. 즉, 아무리 커서 100,000개의 숫자 배열이 들어오고 가장 큰 k가 들어온다고 하더라도 10*100,000=백만번만 연산하면 되는 것이다. k번만큼 선택정렬을 내림차순으로 하게 코드를 짜보았다.

#include <iostream>
using namespace std;

int main()
{
	int arr[100010];
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < k; i++) {
		int inx = i;
		for (int j = i; j < n; j++) {
			if (arr[inx] <= arr[j])
				inx = j;
		}
		int temp;
		temp = arr[i];
		arr[i] = arr[inx];
		arr[inx] = temp;
	}
	
	cout << arr[k - 1];
	return 0;

}