[백준 2075] N번째 큰 수

 

 

문제 설명대로 최대힙을 만들고 n번째까지 빼면서 출력했더니 시간초과가 났다.

 

우선순위큐가 insert, delete 할때 언제나 정렬된다는 성질을 기억해두면 문제에 접근할 수 있다.

 

1. 최소힙을 만든다.

2. i번째 행을 모두 집어넣는다.

3. i+1번째 행을 모두 집어넣고 크기가 n이 될때까지 제거한다.

4. n-1 행까지 2, 3번을 반복한다.

 

최소힙을 구현했으므로 4번까지 진행하면서 작은 수는 모두 제거된다.

남은 수의 개수는 n개 이고 오름차순 정렬이므로 top을 출력해주면 되겠다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++)
                pq.offer(sc.nextInt());
            while(pq.size() > n) {
                pq.poll();
            }
        }
        System.out.println(pq.peek());
    }
}