백준 2075: N번째 큰 수

문제 요약

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다.

표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

문제 분류

• 자료 구조
• 정렬
• 우선순위 큐

문제 풀이

nxn 크기의 수에서 n번째로 큰 수를 찾는 문제이다. vector에 넣고 정렬하는 방법도 있지만, 메모리 초과로 불가능하다. 따라서 우선순위 큐가 필요하다. 이때의 우선순위 큐는 최소 힙이다.

각 행 별로 입력받은 수들을 우선순위 큐에 넣고, 그 큐의 크기를 n으로 맞춰준다. 즉, 큐의 크기가 n을 초과할 경우에 pop연산을 해서 빼준다. 이렇게 함으로써 큐의 원소들은 지금까지 입력받은 수들 중 크기가 큰 n개의 원소들의 집합이 된다. 마지막으로 이 큐의 top을 출력하면, 그 수가 n번째로 큰 수가 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int main()
{
	int n, in;
	priority_queue<int, vector<int>, greater<int>> q;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &in);
			q.push(in);		
		}
		while (q.size() > n) q.pop();
	}
	printf("%d", q.top());

	return 0;
}