Koala - 11기/코딩테스트 준비 스터디

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

nunomi0 2023. 8. 11. 11:33

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

 

2075번: N번째 큰 수

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

www.acmicpc.net

 

# 문제 설명

- N*N의 표에 수가 채워져 있다. 모든 수는 자신의 한 칸 위에 있는 수보다 크다.

- 이러한 표가 주어졌을 때 N번째 큰 수를 출력한다.

- 1<=N<=1500

 

# 풀이 방법

- 우선순위 큐를 이용한다. 메모리 초과 방지를 위해 N개의 원소만 가질 수 있도록 한다.

 

# 정답 코드

#include <iostream>
#include <queue>
using namespace std;

priority_queue<int>pq;
int n, x;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n;
	for (int i = 0; i < n*n; i++) {
		cin >> x;
		pq.push(-x);
		if (pq.size() > n) pq.pop();
	}
	cout << -pq.top();
}