백준, BOJ, 7662번, N번째 큰 수 C++ [CPP] ★★★

 

이 친구는 메모리제한이 빡세다.

그래서.. 새로운 방법을 생각해내야 했다.

 

N이 1500번이라 1500*1500은 충분한데..

공간이 부족하다..?

 

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

---

힙 사이즈를 N으로 고정시켜서 1500 * 1500의 계산을 함에도 메모리가 부족하지 않게 했다.

이 생각을 한 번에 생각할 수는 없었고..

그냥.. N번째 큰수라함은.. 가장 큰 수 5개 중 가장 작은 값이라 생각할 수도 있고

그냥 모든 수 중에서 5개라고 생각할 수도 있다.

 

위에 생각이 문제 푸는데 더 도움이 되었다.

 

 

#맞은 풀이

#include<bits/stdc++.h>

using namespace std;

priority_queue<int, vector<int>, greater<int>> pq; //최소힙

int main(){
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin >> N;
    int mm = N*N;
    while(mm--){
        int x;
        cin >> x;
        pq.push(x);
        if(pq.size() > N)pq.pop();
    }
    
    //가장 큰 수 N개중 가장 작은 값
    cout << pq.top();

    
    return 0;
}