2075번: N번째 큰 수

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


$O(n^2)$

각 열에서 큰 것부터 1개의 수들씩 총 n개만 비교하여 최댓값을 배제하는 방식을 통해 n번째 수를 구한다.

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N = 1500;
int n, a[MAX_N][MAX_N], p[MAX_N], b[MAX_N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i<n; i++)
        for (int j = 0; j<n; j++) scanf("%d", &a[i][j]);
    for (int i = 0; i<n; i++) b[i] = a[n - 1][i], p[i] = n - 1;
    for (int i = 0; i<n - 1; i++) {
        int h = max_element(b, b + n) - b;
        b[h] = p[h] ? a[--p[h]][h] : 0x7fffffff;
    }
    printf("%d", *max_element(b, b + n));
    return 0;
}

$O(n^2lgn)$

$n^2$개의 수를 정렬하고 n번째로 큰 수를 출력한다.

#include<stdio.h>
#include<algorithm>
using namespace std;
const int MAX_N = 1500;
int n, a[MAX_N*MAX_N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i<n*n; i++) scanf("%d", a + i);
    sort(a, a + n*n);
    printf("%d", a[n*n - n]);
    return 0;
}