[BOJ] 2075번 N번째 큰 수 (C++)

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

#include <iostream>
#include <queue>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	priority_queue<long long> pq;
	int n, k;
	cin >> n;
	
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> k;
			pq.push(-k);
			if(pq.size() > n) pq.pop();
		}
	}

	cout << -pq.top() << endl;
	return 0;
}

처음에 vector을 사용해서 풀었는데 메모리 초과가 났고, priority_queue로 바꾼 후 N의 최댓값인 1500*1500인 경우에도 모든 수를 입력받도록 해서 메모리 초과가 났다.

 

priority_queue에 음수로 바꾸어 push한다. 그러면 실제로 가장 작은 수가 top이 되고 pq의 크기가 N보다 커지면 가장 작은 수를 pop하여 메모리를 초과하지 않도록 하였다. 마지막으로 N번째 작은 수는 top에 있는 수 이기 때문에 양수로 바꾸어 출력한다.