[PS] 백준 #2075 N번째 큰 수 문제풀이

[ 문제 풀이 ]

• Problem : 백준 #2075
• 구분 : DS, PQ(우선순위 큐)
• 난이도 : Gold 4
• 풀이 방법 :
  • 우선순위 큐를 사용하면 푸는 방법은 여러가지가 있는데, 주어진 메모리가 12MB로 작기 때문에 N*N인 수를 모두 우선순위 큐에 넣고 돌리면 메모리 초과가 발생합니다.
  • 따라서, 최소힙 구조를 한 우선순위 큐의 front에 위치한 값보다 클 경우에만 input 값을 넣어주고 n개 이상의 값이 들어오면 front 값을 pop 해주면서 n번째 큰 값을 front 위치에 유지시켜 답을 구할 수 있습니다.(단, queue가 비어있을 때는 무조건 넣어줍니다.)
  • 시간 복잡도는 O(N^2logN)입니다.

[ 🤟🏻 Code from ss-won ]

#include <iostream>
#include <queue>
#include <vector>

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

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i=0;i<n*n;i++){
        cin >> input;
        mnq.push(input);
        if(mnq.size() > n)
            mnq.pop();
    }
    cout << mnq.top();
    return 0;
}