2075-N번째 큰 수

www.acmicpc.net/problem/2075

2075번: N번째 큰 수

Priority Queue 와 Min Heap 에 대한 이해가 필요했던 문제입니다.

 

풀이는 다음과 같습니다.

 

1. 데이터를 입력 받으며, N번째 데이터까지 Priority Queue(Min Heap)에 데이터를 삽입합니다.

데이터가 N개 까지 주어졌을때, Priority Queue의 Top 원소는 가장 작은 수 이면서 N번째로 큰 수로 생각할 수 있습니다.

 

2. N+1번째 데이터부터 Priority Queue의 Top 원소와 비교를 하여 해당 데이터가 더 크다면 Priority Queue의 Top원소를 Pop하고 해당 데이터를 삽입합니다.

 

3. Priority Queue의 Top 원소를 출력합니다.

코드

#include <iostream>
#include <queue>
using namespace std;
int main()
{
    ios_base :: sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);

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

    int n;
    cin >> n;
    for(int i = 0; i < n * n; i++)
    {
        int x;
        cin >> x;
        
        if(minq.size() < n)
        {
            minq.push(x);
        }
        else 
        {
            // N + 1 번째 데이터부터 minq의 가장 작은 root 데이터와 비교하여 그보다 작다면
            // minq의 root 데이터를 제거하고 새로 뽑은 데이터를 삽입함
            if(minq.top() < x)
            {
                minq.pop();
                minq.push(x);
            }
        }
    }

    cout << minq.top();
    
    return 0;
}