백준 2075번 N번째 큰 수 (C++)

갈피도 잡히지 않던 문제에 갑자기 깨달음을 얻었을 때 아!!!! 하는 느낌을 받아본 적 있는가?
나는 고등학교 때 수학학원에 다니면서 학원쌤이나 친구랑 문제를 풀거나 설명을 들을 때 이와 같은 느낌을 받아본 적이 많았다.
오늘 약 3년 ~ 4년만에 아~~~!!!!하는 느낌을 받았다...

문제링크

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

설명

n^2의 수들 중 n번째로 큰 수를 출력하는 문제이다.

그냥 n^2개의 수를 입력받고 정렬한 후 출력하면 되지 않나?인데 그러기엔 메모리 제한이 12MB이기 때문에 이와 같은 방법은 사용하지 않는 편이 좋겠다고 생각하고 풀었다.

근데 질문글이나 다른 사람이 난이도기여한 내용을 보니까 sort로도 풀리는 거 같더라... 혹시 몰라서 sort로 푼 내용을 제출해봤는데 난 메모리 초과를 받았다...

내가 생각하는 이 문제의 핵심은 다음과 같다.

1. 모든 수는 자신의 한 칸 위에 수보다 항상 크다.
2. 메모리 제한이 12MB이다.

위 핵심 내용들을 고려하며 열심히 풀어봤지만 MLE를 받아서 질문글을 찾아보다가 엄청난 힌트를 얻었다.

나는 수를 입력받으면서 작은 수들을 지워나가면 메모리 제한은 지킬 수 있지만 그 수가 N번째 큰 수이면 어떻게 해야할 지 계속 고민했었다.

질문글을 찾아보다가 엄청난 힌트를 얻고 깨달았다.

우선순위 큐의 크기를 N으로 유지하면서 N개의 수를 N번 입력받으면 결과적으로 우선순위 큐에는 N^2의 수들 중 가장 큰 수부터 N번째 큰 수까지 담겨있게 된다.

문제를 풀면서 위와 같은 생각을 해야 풀리겠구나 싶었지만 결국 자력으로 떠올리지는 못했다.
기발한 아이디어가 필요한 문제에서는 정말 운도 따라줘야하는 거 같기도하다... 아예 생각 못 할 법한 아이디어는 아니니까...

코드

#include <iostream>
#include <queue>

using namespace std;

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

	int n, num;
	priority_queue<int, vector<int>, greater<int>> pq;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> num;
			pq.push(num);
		}
		while (pq.size() > n)
			pq.pop();
	}
	cout << pq.top();
	return 0;
}