[백준] BOJ2075 - N번째 큰 수 (JAVA)

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

import java.util.*;
import java.io.*;

public class Main
{
    public static void main(String args[]) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        PriorityQueue<Integer> queue = new PriorityQueue<>();

        //queue size는 5까지만 커질 수 있다
        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++){
                int tmp = Integer.parseInt(st.nextToken());
                if(queue.size()<n)
                    queue.add(tmp);
                else{
                    if(queue.peek()>tmp) continue;
                    else{
                        queue.poll();
                        queue.add(tmp);
                    }
                }
            }
        }
        int ans = queue.poll();
        System.out.println(ans);

    }
}

 

슬라이딩 윈도우를 활용한 문제이다.

우선순위 큐의 크기를 n으로 설정하고 새로 들어오는 수가 queue.peek() 한 수보다 작으면 넘기고, 크다면 queue.poll()로 가장 작은 수를 빼내고 새로 추가한다.

전체 map을 돌고 나면 queue.poll()을 하면 n번째 큰 수를 구할 수 있다.