[BOJ/백준][Gold4] 2075 : N번째 큰 수 (C++)

www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

 

[난이도] Gold4

[유형] 우선순위큐

 

[풀이]

메모리 제한이 12MB으로 적으므로 우선순위 큐를 이용해서 푼다.
큐의 크기가 N 이하이면 무조건 push,
아닌 경우 top보다 작은 것들은 무시, top보다 크면 pop하고 push한다
모든 수를 다 봤을 때 top이 정답이다.

 

#include <cstdio>
#include <queue>
#include <vector>
#include <functional>
#include <algorithm>
using namespace std;
int N;
int main(){
    priority_queue<int,vector<int>,greater<int>> a;
    scanf("%d",&N);
    for(int i=0;i<N*N;i++) {
        int v;
        scanf("%d",&v);
        if(a.size()<N) a.push(v);
        else if(a.top() < v) {
            a.pop();
            a.push(v);
        }
    }
    printf("%d",a.top());
}

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2075.cpp