[Java] BOJ 2075: N번째 큰 수

[English]

N**2 Numbers are filled in a N by N size Table. There is a unique characteristic, that every number is bigger than the one above. Take a look at the table when N is 5.

When a table is given like this, Find a Program where you can find a Nth biggest number in the table. Every number in the table is different.

[Input]

In the first line (1<=n<=1500) N is given.

for the next N rows, there are N numbers given. Every number in the table is bigger than or equal to negative billion, and smaller than a billion.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n= Integer.parseInt(br.readLine());
        PriorityQueue <Integer> queue= new PriorityQueue<>();
        StringTokenizer st= null;
        for (int i=0;i<n;i++){
            st=new StringTokenizer(br.readLine());
            for (int j=0;j<n;j++){
                int num=Integer.parseInt(st.nextToken());
                if (queue.size()==n){
                    if (queue.peek()<num){
                        queue.poll();
                        queue.add(num);
                    }
                }

                else queue.add(num);
            }
        }
        System.out.println(queue.poll());
    }
}

BufferedReader를 이용하여 입력을 받고, 우선순위 큐를 이용하여 상위 n개의 숫자를 선택하였다.

먼저 BufferedReader란 Scanner와 같이 입력을 받을때 사용된다. 그러나 더욱 빠른 입출력을 위해서 사용되곤 한다. 말 그대로 '버퍼'를 이용하기 때문에, 버퍼가 가득 차거나 개행 문자가 나타나면 프로그램으로 버퍼의 내용을 한 번에 전송하기 때문에 더욱 효율적으로 입출력을 할 수 있다.

BufferedReader를 사용할 때는

1. main 함수에서 IOException을 Throws해야 한다.

• Throw는 예외를 강제로 발생시키는 것, Throws는 자신을 호출한 메서드에게, 상위 블럭에게 예외를 던지게끔 함
  2, 정수형을 받기 위해서는 Integer.parseInt()로 저장하여야한다.

3. 한 line을 받기 위해서는 StringTokenizer를 이용한다.

또한, PriorityQueue 를 사용하여 Priority Queue를 구현하였다.

pq.qdd()는 priority queue안에 값을 넣는다.
pq.peek()은 priority queue 안에 확인만 하고, 따로 삭제는 하지 않는다.
pq.poll()은 파이썬의 pop과 같은 역할을 하는데, 가장 앞에 있는 값을 return하고 삭제한다.
pq.remove()은 가장 앞에 있는 값을 삭제한다.