C++ - 백준 2075 N번째 큰 수

/* 백준 2075 N번째 큰 수

* 풀이

N x N 개의 숫자에서 N 번째 큰 수를 구하는 방법을 생각해 봐야 한다.

우선 전체 입력값들을 vector 에 넣고 sort 하는 방법을 생각할 수 있는데,
이 경우 시간복잡도가 O(n log n) 이고, 1 <= N <= 1,500 이므로 전체 숫자의 개수는
1,500 x 1,500 개 이므로 시간을 조금 더 줄이는 방법을 고민할 필요가 있을 것 같다.

전략:

    o priority_queue 를 사용해서 크기를 N 으로 유지하면서 삽입/삭제를 진행
    o minimum heap 을 이용하면 마지막에 root에 남아 있는 값이 답이 된다

    이 경우 시간복잡도는 O(log n) 이 된다

생각해보면 
"채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다."
이런 말은 함정이라고 봐야 한다.
*/

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

using namespace std;

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);

	int n;
	cin >> n;

	// 최소 힙 (우선순위 큐)을 사용하여 N개의 큰 수를 저장합니다.
	priority_queue<int, vector<int>, greater<int>> pq;

	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			int num;
			cin >> num;

			// 우선순위 큐의 크기가 N보다 작으면 그냥 넣습니다.
			if (pq.size() < n) {
				pq.push(num);
			} else {
				// 현재 숫자가 큐의 최소값보다 크면, 최소값을 빼고 현재 숫자를 넣습니다.
				if (num > pq.top()) {
					pq.pop();
					pq.push(num);
				}
			}
		}
	}

	// 우선순위 큐의 최소값이 N번째 큰 수입니다.
	cout << pq.top() << '\n';

	return 0;
}