백준 2075 n번째큰수 c++ // 우선순위큐, 발상, 수학

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

2075번: N번째 큰 수

1.의사코드

1. 작은것부터 넣기

2. 메모리제한 -> 큐에n개이상이면 pop 하기

3. top에 있는애가 n번째 큰수임

ex)

1~7에서 5번째 큰수는 3이다.

pq에 6이 올때, 5(n)<6(size) -> top(1제거)

pq에 7이 올때, 5(n)<6(size) ->  top제거(2제거)

이후 top 에있는 놈이 정답인 3이다.

 

2. 전체코드

ios sync 코드를 빠뜨렸더니 시간초과가 났다..

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll ret,n,tmp;
priority_queue<ll,vector<ll>,greater<ll>> pq;

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

	cin >> n;
	for (int i = 0; i < n*n; ++i) {
		cin >> tmp;
		pq.push(tmp);
		if (n < pq.size()) pq.pop();
	}

	cout << pq.top();

	
	return 0;
}