[BOJ] 2075번 - N번째 큰 수

👀 문제 분석

백준 - N번째 큰 수

N x N 표의 $N^2$ 개의 수가 채워져있다.

모든 수는 자신의 한 칸 위에 있는 수보다 크다.

표에서 N번째 큰 수를 찾으면 된다.

입력 조건

• N은 1≤ N ≤ 1,500

⚒️ 설계

1. 우선순위 큐를 생성한다.
2. 배열의 모든 값을 순회하면서 힙의 크기가 N보다 작으면 값을 추가한다.
3. 힙의 크기가 N인 상태에서 새로운 값이 최소값보다 크면 제거하고 새로운 값을 추가한다.
4. 순회를 마치면 최소 힙에서 최소값이 N번째 큰 값이 된다.

📝 코드

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> minHeap = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            
            for (int j = 0; j < N; j++) {
                int num = Integer.parseInt(st.nextToken());

                if (minHeap.size() < N) {
                    minHeap.add(num);
                } else if (num > minHeap.peek()) {
                    minHeap.poll();
                    minHeap.add(num);
                }
            }
        }

        System.out.println(minHeap.peek());
        br.close();
    }
}

⌛️ 시간복잡도

• 배열 순회 : $O(N^2)$
• 힙 연산 : $O(log N)$

👩🏻‍💻 느낀점

우선 순위 큐를 이용해서 어떻게 동작하는 지 이해하고 풀이하니 어렵지 않았다.

✔️ 소요 시간 : 20분