[BOJ] 2075번 N번째 큰 수 - JAVA(자바)

💡 PriorityQueue

2075번: N번째 큰 수

우선순위 큐를 구현하는 방식인 힙(Heap)에서 데이터를 넣었다가 꺼내는 작업은 정렬하는 작업과 동일하다. 이 경우 시간복잡도는 O(NlogN)이 된다.

 

따라서 순서 상관없이 주어진 데이터를 우선순위 큐에 넣기만 하면 루트노드는 가장 우선순위가 큰 값을 가지고 먼저 제거된다. 문제에서는 N번째로 큰 수를 찾는 문제로 Collections.reverseOrder()메서드를 활용하여 높은 숫자가 우선순위가 될 수 있도록 한다.

import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);

        int n = s.nextInt();

        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                q.offer(s.nextInt());
            }
        }

        int count = 1;
        while(count != n) {
            q.poll();
            count++;
        }
        System.out.println(q.peek());

    }
}