BOJ 11004 (K번째 수)

• 문제
  수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.
  
  
• 입력
  첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다.
  둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109)
  
  
• 출력
  A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, K;
vector<int> vi;
void fast_io()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

int main()
{
	fast_io();
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		int num; cin >> num;
		vi.push_back(num);
	}
	sort(vi.begin(), vi.end());
	cout << vi[K - 1];
	return 0;
}

  계속 왜 틀렸나 했는데 K를 입력받지 않았었다. 정렬해야하는 배열 또는 벡터의 최대 크기가 5000000이라 O(N^2)의 시간 복잡도 정렬 알고리즘을 쓰면 시간 초과가 나올 것이다. STL의 algorithm에서 제공하는 sort 함수는 O(NlogN)의 시간 복잡도를 가지므로 이를 활용하면 간단하게 풀 수 있다. (quick sort나 merge sort를 직접 구현해도 되나 원리를 알지 못하면 오래걸릴 것이다.)

시간복잡도 : O(NlogN)