<백준> 2075

N번째 큰 수

문제
N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

입력
첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

출력
첫째 줄에 N번째 큰 수를 출력한다.

최소 힙으로 정렬된 우선순위 큐에 값을 넣고, n보다 사이즈가 커지면 pop을 해 n의 크기를 유지하고, 최솟값으로 정렬된 큐에 맨 앞에 값을 출력한다. 그러면 n번째로 큰 수가 나온다.

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	priority_queue<int, vector<int>,greater<int>> pq;

	for (int i = 0; i < n * n; i++)
	{
		int value;
		cin >> value;

		pq.push(value);

		if (pq.size() > n)
			pq.pop();
	}
	cout << pq.top() << endl;
}