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

문제

2075번: N번째 큰 수

풀이

우선 순위 큐

 

모든 수를 vector에 넣으면 메모리 초과가 발생한다. 수를 입력받으면서 바로 처리해줘야 한다. 

오름차순 우선순위 큐를 만든다. 우선순위 큐는 입력받으면 바로 정렬되므로 top에는 큐에서 가장 낮은 값이 위치하게 된다. 즉, 우선순위 큐의 size를 N으로 제한한 상태에서 i번째 수까지 입력받으면, top에는 i번째 수 중에서 N번째로 큰 수가 위치하게 된다.

코드

#include <iostream>
#include <queue>

using namespace std;

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

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

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            int temp;
            cin >> temp;

            pq.push(temp);
            
            // 우선순위 큐의 사이즈가 N보다 크다면 pop
            // 현재까지 가장 작은 수가 pop된다.
            if (pq.size() > N)
            {
                pq.pop();
            }
        }
    }

    cout << pq.top();

    return 0;
}