[백준 2075번] N번째 큰 수

문제 링크:https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

<문제 풀이> 우선순위 큐, 정렬

[정렬]

12MB이므로 2550000 크기의 배열 만들고 내림차순 정렬 후 N번째 수 출력

 

<C++ 소스 코드>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    vector<int> v(2550000);
    for (int i = 0; i < n * n; i++)cin >> v[i];
    sort(v.begin(), v.end(), greater<int>());
    cout << v[n-1];
    return 0;
}

 

 

 

[우선순위 큐]

 

행마다 N개를 최소 힙에 push ,pop을 반복하면서 힙에 N개를 유지하면 결국 top에 N 번째로 큰 수가 나온다. 

 

<C++ 소스 코드>

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int n;
    cin >> n;
    priority_queue<int, vector<int>, greater<int> > pq;
    
    for (int i = 0; i < n; i++) {
        int data;
        cin >> data;
        pq.push(data);
    }
 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int data;
            cin >> data;
            pq.push(data);
        }
        for (int i = 0; i < n; i++)pq.pop();
    }
    cout << pq.top();
    return 0;
}