백준 11004번 C++ K번째 수

K번째 수

https://www.acmicpc.net/problem/11004

수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오.

문제는 간단해보였는데...

아마 이걸 푸는 사람들을 기다리는 건 시간초과일 것이다.

그냥 알고리즘 헤더에 있는 소트함수로 하면 될 것 같았는데 안 돼서 오늘 Min Heap으로 풀었다.

그랬더니 아슬아슬하게 통과.

radix sort를 이용하면 시간복잡도는 O(dn) (d: 데이터의 가장 큰 자리수, n: 데이터수)이라고 한다. 더 빠르게 풀 수 있을 듯

우선순위 큐 최고...

시간초과 참고는 여기

코드

#include <iostream>
#include <queue>
using namespace std;
int main() {
    int N, K, temp;
    scanf("%d %d", &N, &K);
    priority_queue<int, vector<int>, greater<>> pq;
    for(int i=0; i<N; i++) {
        scanf("%d", &temp);
        pq.push(temp);
    }
    while(K>1) {
        pq.pop();
        K--;
    }
    printf("%d", pq.top());
    return 0;
}