[백준] 2075 - N번째 큰 수

[문제링크]

2075번: N번째 큰 수

 

0. 같은 열에서, 아래에 있는 값은 항상 윗 값보다 크다 = 해당 열의 최댓값은 가장 아래있는 값이다

 

1. 각 열마다 최댓값을 구해서 저장하고, 그중 가장 큰 값부터 하나씩 제외한다

• 쉽고 효율적으로 최댓값을 구하기 위해 우선순위 큐 사용

 

2. 최댓값을 제외할 때 같은 열의 그다음 큰 값, 즉 바로 위의 값을 대신 저장한다

 

3. N번째 제외되는 최댓값이 곧 N번째로 큰 수이므로 구하려는 답이다

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));		
		
		int N = pint(br.readLine());
		int[][] num = new int[N][N];
		int[] idx = new int[N]; //각 열의 idx 관리
		int cnt=0;
		PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				// TODO Auto-generated method stub
				return o2[1]-o1[1];
			}
		});
		
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			idx[i]=N-1;
			for (int j = 0; j < N; j++) num[i][j]=pint(st.nextToken());
		}
		
		for (int i = 0; i < N; i++) pq.add(new int[] {i, num[ idx[i]-- ][ i ]});
		
		while(cnt<N-1) {
			int[] cur = pq.poll();
			int i = cur[0];
			if(idx[i]>=0) { //더이상 값이 없을경우 처리
				int newV = num[ idx[i]-- ][i];
				pq.add(new int[] {i, newV});
			}
			
			cnt++;
		}
		System.out.println(pq.poll()[1]);
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면