(백준) 11004 – k번째 숫자(C++)

질문

11004호: K호 (acmicpc.net)

11004호: K번째 번호

주어진 숫자 N A1, A2, …, AN. A를 오름차순으로 정렬했을 때 앞에서부터 K번째 수를 찾는 프로그램을 작성하시오.

www.acmicpc.net

설명하다

입력 시퀀스를 정렬하고 K번째 요소를 출력하면 됩니다.

시간 복잡도가 $O(N^{2})$인 정렬(예: 버블 정렬)은 N이 5백만 범위에 있기 때문에 사용할 수 없습니다.

하지만 C++에서 기본적으로 제공하는 정렬 기능은 $O(NlogN)$의 시간복잡도를 가지므로 해결할 수 있다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A(i);
    }
    
    sort(A.begin(), A.end());
    cout << A(K - 1);

    return 0;
}