[C++][N 번째 큰 수 2075] 우선 순위 큐

백준 N번째 큰 수

 

문제 힌트

N*N은 의미가 없다.

우선순위 큐를 사용해 푼다.

메모리 초과 조심

 

 

문제 풀이

큰 흐름 : 순서대로 우선 순위 큐에 넣어서 n번째 수 출력

1. 오름 차순 우선 순위 큐에 수 입력 받아 넣는다.

단, n*n 모두 받아 실행하면 메모리 초과 뜬다.

총 n+1개만 남도록 n 초과되면 pop() 한 이후에 입력받은 수를 넣는다.

2. 입력이 끝나면 우선 순위 큐에는 총 n+1개의 원소만 남는다. 하나 팝한 후 top출력

 

 

소스코드

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	priority_queue<int,vector<int>,greater<int>> pq;//오름차순 
	
	for(int i = 0,tmp ; i < n*n ; i++){
		cin>>tmp;
		if(pq.size()>n){
			pq.pop();
		}
		pq.push(tmp);
	}
	pq.pop();
	cout<<pq.top();
}

 

참고

우선순위큐 사용법, 구현법