[백준] 1927번: N번째 큰 수 (Java)

1. 문제설명

NxN의 표에 int 범위의 수가 채워져 있다. 채워진 모든 수는 자신의 한 칸 위에 있는 수보다 크다. 이러한 표가 주어졌을 때 N번째 큰 수를 찾는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 12MB (Java 11: 384 MB)

 

2. 접근 방식

• 우선순위 큐를 사용하여 내림차순으로 표의 모든 값을 저장한다.
• N-1번 큐의 맨 앞의 값을 제거하고, N번째의 값을 출력한다.

 

3. 최종 코드

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

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> pq = new PriorityQueue<>(Collections.reverseOrder());

        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++) {
                pq.offer(Integer.parseInt(st.nextToken()));
            }
        }

        // N-1번 큐의 맨 앞의 값을 제거
        for(int i=0; i<n-1; i++) {
            pq.poll();
        }

        // N번째의 값을 출력
        System.out.println(pq.poll());
    }
}