[BOJ] 2075번: N번째 큰 수

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

메모리 제한이 10MB인데 1500*1500 크기의 배열에 정렬을 해도 메모리 9.9MB에 640ms로 아슬아슬하게 AC를 받는다 ㅋㅋㅋ

아니면 우선순위 큐(pq라고 하겠다)를 이용하는 방법도 있다. pq는 pop할 때 기본적으로 가장 큰 수가 나오기 때문에 pq 크기가 n보다 클 때 계속 pop하면 pq.top은 가장 큰 수(n번째 큰 수)가 남는다.

#include <stdio.h>
#include <queue>
using namespace std;

int n;
priority_queue<int> pq;

int main()
{
    scanf("%d", &n);
    for (int a, i = 0; i < n * n; i++)
    {
        scanf("%d", &a);
        pq.push(-a);
        if (pq.size() > n)
            pq.pop();
    }
    printf("%d", -pq.top());
    return 0;
}

 

#include <cstdio>
#include <algorithm>
using namespace std;

int n;
int ar[2250001];
bool comp(const int &a, const int &b) { return a > b; }
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n * n; ++i)
        scanf("%d", &ar[i]);
    sort(ar, ar + n * n, comp);
    printf("%d\n", ar[n - 1]);
}