[백준] 2075번 - N번째 큰 수 (C++) 문제 및 풀이

문제) 백준 - 우선수위 큐 - N번째 큰 수

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

2075번: N번째 큰 수

 

N * N개의 모든 수를 저장하고 정렬해서 N번째 큰 수를 구하기에는 메모리 제한이 12MB이기에 불가능합니다. 대부분의 정렬 문제는 우선순위 큐로 해결할 수 있습니다. 우선순위 큐를 최소 힙으로 사용하여 문제를 해결했습니다. Input을 최소 힙에 push 하면서 최소 힙이 N개가 되게 유지합니다. 그 후, top을 출력하면 해답을 구할 수 있습니다.

 

C++ 소스코드)

	#include <bits/stdc++.h>
	#define endl "\n"
	#define MAX 1501
	using namespace std;
	typedef pair<int, int> p;
	int N;
	priority_queue<int> pq;
	int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for(int i = 0; i < N * N; ++i){
	int a; cin >> a;
	pq.push(-a);
	if(pq.size() > N)
	pq.pop();
	}
	cout << -pq.top();
	return 0;
	}

view raw 2075.cpp hosted with ❤ by GitHub