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

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 2075번 문제인 N번째 큰 수이다.
문제는 아래 링크를 확인하자.

www.acmicpc.net/problem/2075

2075번: N번째 큰 수

이 문제의 가장 큰 특징은 메모리 제한이다.

메모리제한이 없다면 시도해볼 수 있는 방법이 많겠지만, 이 문제에서는 모든 N을 입력받아서 보관할 충분한 메모리가 주어지지 않는다.

 

다행히도, 이 문제에서는 N^2개의 수 가운데 N번째로 큰 수를 구해주기만 하면 된다. 따라서, 수를 하나씩 입력받으면서 가장 큰 수 N개를 계속 관리해나가는 식으로 문제를 해결할 수 있을 것이다.

 

이를 관리하기 위해 글쓴이는 우선순위 큐(Priority Queue)를 활용하였다.

N+1개의 수가 우선순위 큐에 있는 상태에서 가장 작은 수를 제거할 수 있기 때문이다.

 

아래는 제출한 소스코드이다.

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

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

    priority_queue<int> pq;

    int N; cin >> N;
    for (int i = 0;i < N;i++) {
        int x; cin >> x;
        pq.push(-x); // min heap으로 활용하기 위한 마이너스 부호
    }

    int NN = N * N;
    for (int i = N;i < NN;i++) {
        int x; cin >> x;
        pq.push(-x); 
        pq.pop();
    }

    cout << -pq.top();
}