BOJ 2075: N번째 큰 수

#BOJ 2075: N번째 큰 수

2075번: N번째 큰 수

#풀이

입력 받는 숫자를 정렬하여 N번째 큰 숫자를 출력하는 문제이다.

하지만 문제에서 메모리제한이 작게 걸려 있어서 최소한의 메모리를 사용해야 하는 문제이다.

 

맨 처음에는 그냥 입력 받은 모든 수를 저장하고 정렬하여 출력했는데 어김없이 메모리초과 가 발생하였다.

 

우선순위큐를 사용하여 최소힙을 사용하여 루트가 N번째 큰 수가 되도록 하였다.

 

우선순위 큐 특성상 이진트리이므로 항상 정렬이 되어 있다.

입력받고 queue에 push를 한 다음 queue의 사이즈가 N개가 넘어가면 루트값을 지워 queue에는 N개의 요소가 있게 유지하였다.

 

#코드

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
int n;
priority_queue<int, vector<int>, greater<int>> q;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int num;
			cin >> num;
			q.push(num);
			if (q.size() > n) {
				q.pop();
			}
		}
	}

	cout << q.top() << '\n';
	return 0;
}