[BOJ] 2075번 : N번째 큰 수(C++)

문제 링크 : 백준 2075번

[문제 접근]

처음에 메모리 제한을 보지 못하고 1<=n<=1500 이길레 그냥 정렬해서 풀었더니 메모리 초과가 발생했다.

따라서 우선순위 큐를 이용하는데 숫자가 작은 것이 우선순위가 높은 것으로 설정해주고 큐에 n개 이상 들어오지 못하게 작은 숫자들을 계속 pop하면 최종적으로 큐에 큰 숫자 상위 n개 만큼 남게된다.

[소스 코드]

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;
int n;
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i=1 ; i<=n ; i++) {
        for(int j=1 ; j<=n ; j++) {
            int a;
            cin >> a;
            pq.push(a);
            if(pq.size()>n) {
                pq.pop();
            }
        }
    }
    cout << pq.top();

    return 0;
}