이번 문제는 우선순위 큐를 사용하여 N번째로 큰 수를 구하는 문제이다. 유의할 점은 메모리 제한이 12 MB라는 점이다. 처음에는 메모리 제한을 신경쓰지 않고 구현했다.

• 우선순위큐를 큰 순서대로 정렬되도록 선언한다.
• N-1번 만큼 pop하고 top을 return한다.

이렇게 하면 원하는 답은 구할 수 있지만 메모리 제한에 걸리게 된다. 메모리를 줄이려면 우선순위큐의 크기를 줄여야한다.

• 우선순위큐를 작은 순서대로 정렬되도록 선언한다.
• 배열 값을 우선순위큐에 넣기 전에 우선순위큐의 크기를 고려한다.
• 크기가 크다면 넣으려는 배열 값보다 우선순위큐의 top이 작다면 배열 값을 push해주고 pop해준다.
• 크기가 작다면 배열 값을 push해준다.

Code

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

int n;
int a;
priority_queue<int, vector<int>, greater<>> pq;


void Input(){
    cin>>n;
    for(int i=0; i<n*n; i++){
        cin>>a;
        if(pq.size()<n){
            pq.push(a);
        }
        else if(pq.top()<a){
            pq.push(a);
            pq.pop();
        }
        else
            continue;
    }
}

int Solution(){
    return pq.top();
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    cout<<Solution()<<endl;
    return 0;
}