[자료구조2] 백준 2075 N번째 큰 수

2075번: N번째 큰 수

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

 

# 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        // 빠른 입출력을 위한 BufferedReader 와 StringBuilder
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // N
        long n = Long.parseLong(br.readLine());

        // N^2 개의 수를 담는 PriorityQueue (우선순위 큐)
        // 우선순위가 높은 숫자가 먼저 나온다. [reverseOrder() : 큰 숫자부터]
        PriorityQueue<Long> pq = new PriorityQueue<>(Collections.reverseOrder());

        for (long i = 0; i < n; i++) {
            // 문자열 분리를 위한 StringTokenizer
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");

            for (long j = 0; j < n; j++) {
                pq.offer(Long.parseLong(st.nextToken()));
            }
        }

        // N번째 큰 수
        for (long i = 0; i < n-1; i++) {
            pq.poll();
        }
        sb.append(pq.poll());

        System.out.println(sb);

        // Reader 버퍼 닫기
        br.close();
    }
}

• PriorityQueue (우선순위 큐) : 들어가는 순서와 상관없이 우선순위가 높은 데이터가 먼저 나가는 자료구조
• JAVA의 우선순위 큐는 힙(Heap) 방식으로 구현되어 있다고 한다.

 

아래는 PriorityQueue의 주요 메소드이다.

• offer() : 우선순위 큐에 원소를 추가 (실패 시 false 반환)
• poll() : 우선순위 큐에서 첫 번째 값을 반환하고 제거 (비어있다면 null 반환)
• peek() : 우선순위 큐에서 첫 번째 값을 반환만 하고 제거하지는 않음 (비어있다면 null 반환)

 

추가로 사용할 수 있는 비슷한 메소드이다. 실행 실패 시 offer, poll, peek 은 null을 반환하고, add, remove, element 은 예외를 발생시킨다는 차이가 있다.

• offer - add
• poll - remove
• peek - element