[C++][백준 2075] N번째 큰 수

[문제]

2075번: N번째 큰 수 (acmicpc.net)

2075번: N번째 큰 수

---

[문제 풀이]

priority queue(우선 순위 큐)를 이용한 간단한 문제이다.

우리들은 N번째 큰 수라고 하면 알아낼 수 있는 자료구조는 매우 드물다.

하지만 N이라는 사이즈의 크기를 가진 자료구조 형태에서 가장 마지막 혹은 가장 첫번째 있는 원소를 가져오라고 하면 어렵지 않게 구할 수가 있다.

 

그러니 N이라는 사이즈를 가진 우선순위 큐를 만들도록 하자.

나는 우선 순위 큐의 사이즈 자체를 한정 짓는 방식을 알지 못하기 때문에 만일 우선 순위 큐의 사이즈가 N보다 커진다면 원소를 pop 하도록 만들었다.

---

[코드]

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

#define endl "\n"

using namespace std;

int main(){
    cin.tie(), ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    int temp;
    priority_queue<int,vector<int>,greater<int> > pq;
    for(int i = 0;i<n * n;i++){
        cin>>temp;
        pq.push(temp);
        if(pq.size()> n){
            pq.pop();
        }
    }
    cout<<pq.top()<<endl;
    return 0;
}