[baekjoon 2075] N번째 큰 수 (우선순위큐, 정렬) (C++)

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

2075번: N번째 큰 수

이런 표가 주어지고, 같은 열에 있는 수는 아래로 갈수록 커지는 특징이 있다.

이런 수의 구성 중에서 N번째 큰 수를 찾는 것이다.

이 문제의 메모리 제한은 4MB로, 모든 수를 입력받아서 정렬 후 N번째를 찾는 방법은 메모리 초과가 날 것으로 예상되었다. (N은 1500개까지)

 

따라서, 우선순위 큐나 벡터+정렬을 이용해서 한 줄을 입력받고 정렬한다.

이후에, 거기서 N개의 수만 남기고 모두 pop 한다.

그렇게 되면 수를 담는 자료구조에는 항상 n개의 수만 남아있고 이 과정을 모든 수에 적용하면 마지막에 남은 n개의 수가 제일 큰 수부터 n번째 큰 수가 된다.

 

과정 1) 5 7 9 12 15

과정 2) 5 6 7 8 9 11 12 13 15 19 (작은 5개 삭제)

과정 3) 10 11 12 13 15 16 19 21 26 31

과정 4) 14 16 19 21 25 26 28 31 35 48

과정 5) 20 26 28 31 32 35 41 48 49 52

남은 수 중 가장 작은 수가 N번째 작은 수로 35가 된다.

 

#include <iostream>
#include <queue>

using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
// greater -> 오름차순 = 최소힙
int N, num;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	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();
}