[백준] 2075번 N번째 큰 수

 

[적용한 알고리즘]

우선순위 큐

 

[아이디어]

우선 순위 큐의 크기를 N개로 항상 유지해줘야겠다.

메모리가 개빡셈.

 

[생각의 흐름 / 절차] 

1. 우선순위 큐의 크기를 N개로 유지해줘야겠다. (min-heap)

2. 매 한 열씩 돌면서 pq에 넣어주고, N개만큼 pop해주자.

3. 그럼 마지막에 남는 pq의 top에는 딱 N번째 숫자가 있을 것이다.

 

[교훈]

메모리 관리는 배열의 크기를 최대한 줄이는 걸로 시작하자.

 

<코드>

#include <cstdio>
#include <queue>
#include <algorithm>
#define max 1501
using namespace std;

int main(){
    int n;
    int a[max][max] = { 0 };
    priority_queue<int, vector<int>, greater<int>> pq;

    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++){
        pq.push(a[i][0]);
    }
    for (int j = 1; j < n; j++){
        for (int i = 0; i < n; i++){
            pq.push(a[i][j]);
        }
        for (int i = 0; i < n; i++){
            pq.pop();
        }
    }

    printf("%d", pq.top());
    return 0;
}