[C++] 백준 2075번 N번째 큰 수

www.acmicpc.net/problem/2075

2075번: N번째 큰 수

힙 혹은 우선순위 큐에 대해서 공부를 하기 위해서 문제를 찾던 도중 발견한 문제이다.

 

그냥 기본적인 우선순위 큐를 사용해서 푸는 문제인데 메모리 제한이 있어서 이부분을 생각해

pop()을 넣어주는 것이 중요한 문제였다.

 

또한 시간 초과를 겪었는데 이 부분은 cin, cout을 사용할 경우

ios_base :: sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

위와 같은 코드를 삽입해주어야 하고 아니면 그냥 scanf, printf를 사용해야 시간 초과가 나지 않는다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;

int main() {
	int n, x;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%d", &x);
			pq.push(x);
			if (pq.size() > n) {
				pq.pop();
			}
		}
	}
	printf("%d", pq.top());
	return 0;
}

왜 난이도가 골드 4인지 약간 이해가 안되는 문제였다.. 아마 우선 순위 큐를 사용하지 않고 직접 구현하는 경우를 생각해서 그런 것 같다.