[백준 2075] N번째 큰 수

요구사항

n*n이 주어졌을대 n번째 큰 수를 구하라

 

풀이

메모리 제한이 12MB이므로 [1500][1500]배열도 선언할 수 없고, vector의 크기도 1500*1500가 될 수 없다

단순히 우선 순위 큐의 크기를 n만큼으로 제한하여서 문제를 해결할 수 있다.

n개의 최소 힙을 선언하여 n개의 최소보다 더 크다면 pop한 후, 다시 넣을 수 있도록 한다

 

#include <iostream>
#include <queue>
#include <functional>
#include <algorithm>
#include <vector>
using namespace std;

priority_queue<int, vector<int>, greater<> > q;
int n;
vector<int> v;
int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int x;
			scanf("%d", &x);
			if (q.size() < n) {
				q.push(x);
			}
			else if(q.size()==n) {
				int NowNumber = q.top();
				if (NowNumber < x) {
					q.pop();
					q.push(x);
				}
			}
		}
	}
	
	cout << q.top() << endl;
}