BOJ 2075 - N번째 큰 수

www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

메모리 제한이 있는 문제여서 단순히 이차원배열이나 벡터를 쓰면 메모리 초과가 발생한다.

 

이 문제를 풀기위한 핵심 아이디어는, 입력받은 모든 값을 메모리에 저장하는게 아니라,

최소힙을 이용해서 N 개 만큼만 받은뒤, N 개 이상의 입력이 들어오는 경우,

최소힙에 담긴 가장 작은 값과 비교해서 더 크면 추가해주는 방식으로 쭉 배열을 돌리면

결국 N 개만 최소힙에 남게되고,

가장 큰 것 ~ N번째로 큰 것 만 최소힙에 남게된다.

그러므로 마지막에 최소힙의 top 을 뽑아내면 답이된다.

 

 

 

- c++

#include <bits/stdc++.h>
 
using namespace std;
 
int N;
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    
    priority_queue<int, vector<int>, greater<int>> pq;
    
    int temp;
    for (int i = 0; i < N * N; ++i) {
        cin >> temp;
        if (pq.size() < N) pq.push(temp);
        else {
            int num = pq.top();
            if (num < temp) {
                pq.pop();
                pq.push(temp);
            }
        }
    }
    
    cout << pq.top();
    
    return 0;
}