[백준] 2075번 : N번째 큰 수 – JAVA [자바]

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

 

 

 

---

문제

 

 

---

해결 방법

이 문제를 해결하는 가장 직관적인 방법은 N×N개의 숫자를 정렬한 후 N번째 큰 값을 찾는 것이다. 하지만 이는 O(N² log N²) = O(N² log N)의 시간 복잡도를 가지므로, N = 1500인 경우 비효율적일 수 있다.

이를 해결하기 위해 우선순위 큐(PriorityQueue)를 활용하여 메모리를 절약하고 실행 속도를 개선할 수 있다.

최적화 방법 (최소 힙 사용)
1. 최소 힙(PriorityQueue)을 사용하여 최대 N개의 숫자만 저장
2. 처음 N개의 숫자는 힙에 삽입
3. N+1번째 숫자부터는 힙의 최솟값(peek)보다 크면 교체
4. N×N개의 숫자를 모두 처리한 후, 힙의 최솟값이 N번째 큰 수

이 방식의 시간 복잡도는 O(N² log 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> pq = new PriorityQueue<>(); // 최소 힙

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            while (st.hasMoreTokens()) {
                int num = Integer.parseInt(st.nextToken());
                if (pq.size() < n) {
                    pq.add(num);
                } else if (pq.peek() < num) { // 현재 최소값보다 크면 교체
                    pq.poll();
                    pq.add(num);
                }
            }
        }

        System.out.println(pq.poll()); // N번째 큰 수
    }
}

 

 

---

시간 복잡도 분석

1. 우선순위 큐 삽입 연산
- 각 숫자를 삽입할 때 O(log N)이므로 O(N² log N)

2. 최소 힙 크기를 N으로 유지하면서 교체 연산 수행
- O(N² log N)로 동일하지만, 메모리 사용량 감소

결론: O(N² log N)으로 기존 방식과 성능은 같지만 메모리 효율성 증가한다.