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();
}