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

by

쉬운 목차

문제

11004호: K번째 번호(acmicpc.net)

11004번: K번째 번호

'추천 관련글,

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

www.acmicpc.net

설명

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

시간 복잡도가 $O(N^{2})$인 정렬(예: 버블 정렬)은 N 범위가 500만이므로 사용할 수 없습니다.

하지만 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;
}