[ 백준 / C++ ] 2075 : N번째 큰 수

[ 문제 ]

 

2075번: N번째 큰 수 (acmicpc.net)

 

[ 접근방법 ]

 

일단 우선순위 큐에 n번째 행의 값들을 넣는다.

 

그 후 큐에서 최대값을 추출하고, 추출한 값의 한칸 위에 있는 값을 큐에 넣는 과정을 반복한다.

 

각 과정은 log N 의 시간복잡도를 가지므로 총 O(N log N)의 시간복잡도를 가진다.

 

[ 소스코드 ]

 

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

using namespace std;

int n, arr[1505][1505], idx[1505];
pair<int, int> ans;
priority_queue<pair<int, int>> pq;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0; i < n; i++)for(int j = 0; j < n; j++)cin >> arr[i][j];

    for(int i = 0; i < n; i++){
        idx[i] = n - 1;
        pq.push({arr[idx[i]--][i], i});
    }

    for(int i = 0; i < n; i++){
        ans = pq.top();
        pq.pop();

        if(idx[ans.second] < 0)continue;
        pq.push({arr[idx[ans.second]--][ans.second], ans.second});
    }

    cout << ans.first;

    return 0;
}