[BOJ/C++] N번째 큰 수(2075번)

1. 개요

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

2075번: N번째 큰 수

1-1. 설명

N x N의 표에 수 N^2개가 채워져 있다. 이때 채워진 수에는 특징이 있는데, 모든 수는 자신의 한칸 위에 있는 수보다는 크다. N x N 표가 주어졌을 때 N번째 큰수를 찾는 프로그램을 작성한다. 표에 채워진 수는 모두 다르다.

1-2. 제한 사항

 - 첫 줄에 N이 주어지며, N은 1 이상 1,500 이하

 - 다음 N개 줄에 각 줄마다 N개의 수가 주어지며, 이 수는 -10억 이상, 10억 이하

---

2. 구현

2-1. 풀이

메모리가 매우 제한적(12MB)이라 메모리 풀을 사용할 수 없었다. 다른 방법을 생각하던 중, 우선순위 큐를 이용해 큰수는 뒤로 보내야겠다고 생각했으나 메모리에 제한을 어떻게 해결해야할지 생각을 못하였다. 숫자를 N개만큼 받고 나머지는 받으면서 제일 작은 수는 큐에서 빼면 된다는 풀이를 보고 이를 구현하였다. 

2-2. 코드

#include <iostream>
#include <queue>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, num;
    cin >> N;

    priority_queue<int, vector<int>, greater<int>> queue;
    
    for (int i = 0; i < N * N; i++) {
        cin >> num;
        queue.push(num);
        if (i >= N) queue.pop();
    }
    cout << queue.top() << "\n";

    return 0;
}