BOJ)2075 N번째 큰 수

문제:icpc.me/2075

N^2개의 수가 들어올 때 N번째로 큰 수를 구하는 문제이다.

N이 최대 1500 밖에 안들어오므로 단순히 값을 다 받아서 정렬해주는 N^2logN의 해법으로 해결할 수 있다.

하지만 메모리제한이 10MB이므로 힙을 이용하여 수를 받을 때 마다 큰 수 N개만큼만 저장해주고 그 수들중 가장 작은 수와 들어오는 수를 비교를하여 힙을 관리해주면 된다.

#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n, x;
priority_queue<int> pq;
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n*n; i++) {
        scanf("%d", &x);
        if (pq.size() < n)
            pq.push(-x);
        else {
            if (-pq.top() < x) {
                pq.pop();
                pq.push(-x);
            }
            else
                continue;
        }
    }
    printf("%d\n", -pq.top());
    return 0;
}