백준 2075번 N번째 큰 수 (c++)

N*N (N <= 1500) 개의 수가 input으로 들어오고 여기서 N번째 큰수를 찾는 문제이다.

2가지 방법으로 문제를 해결할 수 있다.

1. 단순히 N^2 개의 input을 정렬하여 N번째 큰수를 출력하는 방법이다.

int는 4byte이고 N^2의 최고 값은 2,250,000 이므로 최대 9MB의 메모리를 사용한다. 메모리 제한의 12MB를 넘기지 않는 크기 이므로 정렬해서 푸는것도 가능하다. 가장 간단한 방법이고 코드 또한 길게 작성할 필요가 없다. 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int arr[2250010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i < n * n; i++)
    {
        cin >> arr[i];
    }
    sort(arr, arr + n * n);
    cout << arr[n * n - n] << endl;
    return 0;
}

2. Priority Queue를 이용하 푸는 방법이다.

처음에 Priority Queue에 N개를 추가한다. 

이후 N개를 추가하고 N개를 제거하는 방식으로 Loop를 진행하면, 최종적으로 Priority Queue에 상위 N개의 값이 남게 된다. 전부 Priority Queue에 push하게 되면 메모리가 초과하게 되니, 한줄씩 넣고 지우고를 반복하는 방법이다. 약간은 번거로워지나, 1번 풀이보다 메모리를 더 아낄 수 있다. 

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct cmp
{
    bool operator()(int a, int b)
    {
        return a > b;
    }
};
int arr[2250010];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    // 2. priority queue 풀이
    priority_queue<int, vector<int>, cmp> pq;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int input;
            cin >> input;
            pq.push(input);
        }
        //상위 n개만 남긴다.
        while (pq.size() > n)
        {
            pq.pop();
        }
    }
    cout << pq.top() << endl;
    return 0;
}