문제 출처

단계별로 풀어보기 > 우선순위 큐 > N번째 큰 수
https://www.acmicpc.net/problem/2075

문제 설명

NxN개의 수가 주어질 때, N 번째로 큰 수를 출력하라.

접근 방법

해당 수들을 받아서, PriorityQueue에 삽입한다. 이 때, PriorityQueue는 내림차순 정렬을 위해, Collections.reverseOrder()를 넣어 생성한다.

import java.io.*;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class N번째_큰_수 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());

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

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

        for(int i = 0; i < N-1; i++){
            pq.poll();
        }
        bw.write(String.valueOf(pq.poll()));
        bw.flush();
        bw.close();
        br.close();
    }
}

알게된 점

시간 복잡도는 O(N^2 log N)이다.

문제푼 흔적