[백준/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()로 최솟값을 확인할 때 큐 전체 순서는 중요하지 않으므로, 큐의 내부 순서가 정렬되지 않아도 괜찮습니다.