[백준 2075번] N번째 큰수

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

package datastructure;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class DataStructure2075 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PriorityQueue<Long> queue = new PriorityQueue<>();

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

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                queue.add(Long.parseLong(st.nextToken()));
            }
            if (queue.size() > N) {
                while (queue.size() != N) {
                    queue.poll();
                }
            }
        }

        System.out.println(queue.poll());
    }
}

 

전형적인 우선순위 큐 문제로 접근할 수 있다. 처음에는 모든 데이터를 List에 넣어 오름차순 정렬한 뒤 정답을 출력하려 했으나, 메모리 초과가 발생할 가능성이 있어 우선순위 큐를 활용하기로 했다.

예를 들어, N=5N = 5N=5일 때, 첫 번째 차례에 5개의 데이터를 우선순위 큐에 넣는다. 이후 두 번째 차례에서는 새로운 데이터를 추가하면서, 큐의 크기가 NNN을 초과하지 않도록 가장 작은 값을 제거해 나간다.

이 방식을 사용하면 메모리 초과 없이 문제를 해결할 수 있다. 마지막에는 queue.poll()을 호출해 정답을 출력하면 된다. 간단하면서도 효율적인 풀이 방식이다.