백준 2075번 N번째 큰 수 [Java]

문제

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

 

입력

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

 

출력

첫째 줄에 N번째 큰 수를 출력한다.

 

예제

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
 
public class Main_BJ_2075_N번째큰수 {
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>() {
 
            @Override
            public int compare(Integer o1, Integer o2) {
                // TODO Auto-generated method stub
                return Integer.compare(o1, o2) * -1;
            }
        });
        
        int N = Integer.parseInt(br.readLine());
        
        for(int i=0;i<N;i++) {
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<N;j++) {
                pq.add(Integer.parseInt(st.nextToken()));
            }
        }
        
        for(int i=0;i<N-1;i++) pq.poll();
        
        System.out.println(pq.poll());
    }
 
}
 

 

구현방법

첫 번째로는 PriorityQueue에 값을 넣어서 while()문을 통해 N번째 큰 수를 찾는 방법으로 구현했습니다.

 

두 번째로는 N번째로 큰 수를 찾는 문제이니 PriorityQueue에 오름차순이 아닌 내림차순으로 정렬하여 값을 넣은 뒤, N번째 큰 수를 찾는 방법으로 구현했습니다.