[백준 2075] N번째 큰 수

문제

• 백준 2075

유형

• 자료구조
• 우선순위 큐

풀이

유형이 우선순위 큐라고 나와있지만 문제에서 주어진 자신의 한 칸 위에 수보다 크다는 특징을 이용하여 표의 제일 밑에서 부터 비교하면서 올라오는 방식으로 풀이하였다.

일단 각 열의 제일 밑 인덱스를 가지는 배열을 하나 만들고 그 배열의 인덱스들에 있는 값을 비교하였다. 만약 2번째 인덱스의 값이 제일 클 때 위 배열의 2번째 인덱스 값을 하나 낮춰서 그 다음 값과 비교할 수 있게 하였다.

말로는 설명이 잘 안되지만 코드를 보면 바로 알 수 있다.

코드

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;
int n;
int arr[1501][1501];
int v[1501];

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);

	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) cin >> arr[i][j];
		v[i] = n - 1;
	}

	for (int i = 0; i < n; i++) {
		pair<int, int> m = { -1e9 - 1, 0 };
		for (int j = 0; j < n; j++) {
			if (v[j] >= 0 && m.first < arr[v[j]][j]) {
				m.first = arr[v[j]][j];
				m.second = j;
			}
		}
		v[m.second]--;
		if (i == n - 1) cout << m.first;
	}

	return 0;
}