[C++] 백준 2075. N번째 큰 수

🌽 문제

🥕 입출력

🥔 풀이

priority_queue 사용법을 고새 잊어먹어서 감자록을 뒤져봤다.
priority_queue<자료형, 구현체, 비교연산자> 기억허자.
모든 입력을 다 받을 경우 최대 1,500 x 1,500 = 2,250,000로 메모리 초과다.

따라서,

1. N개만 저장하는 힙을 만들고
2. 힙의 크기 < N 이면 모두 입력 받는다.
3. 힙의 크기 >= N 일 땐,
   힙의 최솟값보다 더 큰 값이 들어오면 최솟값을 버리고
   더 큰 값을 힙에 저장한다.
4. 모든 입력값을 검토한 뒤 저장된 힙의 최솟값이 답이 된다.

🥬 코드

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

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, tmp;
	cin >> n;
	priority_queue<int, vector<int>, greater<int>> pq;
	for (int i = 0; i < n * n; i++) {
		cin >> tmp;
		if (pq.size() < n)
			pq.push(tmp);
		else {
			if (pq.top() < tmp) {
				pq.pop();
				pq.push(tmp);
			}
		}
	}
	cout << pq.top();

	return 0;
}

🥜 채점