백준 2075: N번째 큰 수(JAVA)

 

💡 문제 요약

• N x N 크기의 2차원 배열이 주어진다.
• 이 배열에서 N번째로 큰 수를 찾아 출력하는 문제

---

📅 조건 요약

• 배열은 총 N개의 줄, 각 줄마다 N개의 정수가 주어진다.
• 모든 수는 정수이며, 중복 가능
• 시간 제한: 1초 / 메모리 제한: 12MB

---

🔍 입력 형식

N
A[1][1] A[1][2] ... A[1][N]
A[2][1] A[2][2] ... A[2][N]
...
A[N][1] A[N][2] ... A[N][N]

• 1 <= N <= 1500

---

✅ 출력 형식

• N번째로 큰 수 출력

---

🧠 알고리즘 설계

1. PriorityQueue (최소 힙) 를 사용하여 최대 N개의 원소를 유지
2. 배열의 모든 수를 순회하면서
   • 힙에 추가
   • 크기가 N을 초과하면 가장 작은 수 제거 (poll())
3. 마지막에 peek()하면 N번째 큰 수가 남게 됨

---

🗂 전체 코드

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

public class N번째큰수 {
    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<>();

        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());
                pq.offer(num);
                if (pq.size() > N) {
                    pq.poll();
                }
            }
        }

        System.out.println(pq.peek());
    }
}

---

⏱️ 시간 복잡도

단계	시간
전체 탐색	O(N^2)
힙 삽입/삭제	O(log N)
총 복잡도	O(N^2 log N)

➡ N <= 1500 이므로 통과 가능

✅ 주요 메서드 요약

메서드	설명
add(E e)	큐에 요소를 추가합니다. (공간 부족 시 예외 발생)
offer(E e)	큐에 요소를 추가합니다. (add()와 유사하나 실패 시 false 반환)
poll()	우선순위가 가장 높은 요소를 제거하고 반환 (비어 있으면 null)
remove()	poll()과 유사하나, 큐가 비어 있으면 예외 발생
peek()	가장 높은 우선순위 요소를 제거하지 않고 반환 (비어 있으면 null)
element()	peek()과 유사하나, 큐가 비어 있으면 예외 발생
size()	현재 큐의 요소 개수를 반환
isEmpty()	큐가 비어 있는지 여부 반환
clear()	큐의 모든 요소 제거
contains(Object o)	특정 요소 포함 여부 확인
toArray()	큐의 요소들을 배열로 반환
iterator()	큐의 요소들을 순회할 Iterator 반환 (정렬 순서 아님)

---

🔄 우선순위 설정 방법

• 기본: 오름차순 (Min-Heap)
• PriorityQueue<Integer> pq = new PriorityQueue<>(); // 기본 min-heap
• 내림차순: Max-Heap
• PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
• 사용자 정의 정렬:
• PriorityQueue<String> pq = new PriorityQueue<>((a, b) -> b.length() - a.length());

---