[백준/JAVA] 2075번 : N번째 큰 수

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

 

[ 문제 요약 ]

N×N 크기의 표가 주어지며, 표의 모든 수는 자신의 위에 있는 수보다 크다는 특징이 있습니다. 이 표에서 N번째로 큰 수를 찾아야 합니다.

 

문제에서 요구하는 것은 단순히 전체 표를 정렬해서 특정 위치의 값을 출력하는 것과는 조금 다릅니다. 큰 값이 상위에 있고, 작은 값이 아래쪽에 있다는 특징을 활용하여, 효율적으로 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());
        int[][] arr = new int[N][N];

        for(int i = 0; i < N; i++) {
            // 12 7 9 15 5
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                int num = Integer.parseInt(st.nextToken()); // 12
                arr[i][j] = num;
            }
        }
        // arr[0][0] = 12, arr[0][1] = 7...
        // arr[1][0] = 13, arr[1][1] = 8...
        // 배열 내림차순 정렬
        Arrays.sort(arr, Collections.reverseOrder());

        System.out.println(arr[0][0]);

    }
}

 

 

📌 기존 코드의 문제점

 

1. 2차원 배열 정렬 문제

원래 코드는 Arrays.sort()와 Collections.reverseOrder()를 사용해 2차원 배열 arr을 내림차순 정렬하려고 시도했습니다. 하지만 Arrays.sort()는 1차원 배열에만 사용할 수 있고, Collections.reverseOrder()는 Comparable 객체에 적용되므로 int[][] 배열에는 사용할 수 없습니다.

 

2. N번째 큰 수 찾기 문제

문제에서 요구하는 것은 표 전체를 내림차순 정렬하여 첫 번째 값이나 가장 큰 값을 찾는 것이 아니라, N번째로 큰 값을 찾는 것입니다. 초기 코드에서는 단순히 정렬 후 첫 번째 값을 반환했기에 이 요구사항을 충족하지 못했습니다.

 

---

[ 정답 코드 & 올바른 풀이 ]

 

📌 올바른 풀이

 

1. 2차원 배열 정렬 문제 해결

2차원 배열의 모든 요소를 정렬하는 대신 필요한 상위 N개의 큰 값만 유지하는 방식으로 수정해야 했습니다.

 

 

2. N번째 큰 수 찾기 문제 해결

PriorityQueue를 사용하여 상위 N개의 큰 값만 남기고, 최솟값을 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++) {
            // 12 7 9 15 5
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++) {
                int num = Integer.parseInt(st.nextToken()); // 12
                // 첫번째 행 큐에 추가
                // [5,7,9,12,15]
                // 두번째 행 큐에 추가
                // 13추가 --> 큐 최솟값 5제거후 추가 [7,9,12,15,13]
                // 8추가 --> 큐 최솟값 7제거후 추가 [9,12,15,13,8]
                // 11추가 --> 큐 최솟값 8제거후 추가 [9,12,13,15,11]
                // 19추가 --> 큐 최솟값 9제거후 추가 [11,12,13,15,19]
                // 6추가 --> 큐 최솟값 11보다 작으므로 큐 그대로 유지

                // (※우선순위 큐에 있는 원소들은 최솟값만 보장될 뿐,
                // 나머지 원소들이 순서대로 정렬되지 x)

                // 이후 행들 계속 반복하면 최솟값 다 제거 후 상위 5개 값만 남게 됌

                // 큐 크기가 N보다 작으면 그냥 추가
                if(pq.size() < N) {
                    pq.add(num);
                // 큐 크기가 N 이상일 경우
                }else if(num > pq.peek()) {
                    pq.poll(); // 최솟값을 제거
                    pq.add(num); // 새 값을 추가
                }
            }
        }

        // N번째 큰 수는 큐의 최상위 원소
        System.out.println(pq.peek());
    }
}

PriorityQueue는 내부에서 자동으로 최소 힙(min-heap) 구조를 유지합니다. 최소 힙에서는 최솟값이 최상위(루트)에 위치하지만, 나머지 원소들의 순서는 반드시 정렬되지 않습니다. 즉, 큐에 있는 원소들은 최솟값만 보장될 뿐, 나머지 원소들이 순서대로 정렬되지 않을 수 있습니다.

 

따라서 PriorityQueue에서 peek()로 꺼내는 최상위 값은 항상 가장 작은 값이지만, 큐 내 나머지 원소들의 순서는 정렬되지 않을 수 있습니다.

 

문제에서 중요한 것은 PriorityQueue의 크기를 N으로 유지하면서 N개의 큰 수 중 최솟값이 N번째 큰 수가 되도록 하는 것입니다. peek()로 최솟값을 확인할 때 큐 전체 순서는 중요하지 않으므로, 큐의 내부 순서가 정렬되지 않아도 괜찮습니다.