문제
N×N의 표가 있다. 각 행과 열은 오름차순으로 정렬되어 있다. 이 표에서 N번째 큰 수를 찾는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,500) 이후 N개의 줄에는 N개의 수가 주어진다. 표에 있는 수는 절댓값이 10^9보다 작거나 같은 정수이다.
출력
N번째 큰 수를 출력한다.
예제
입력:
3
1 5 7
2 3 8
3 5 9출력:
7풀이
핵심 아이디어: N번째 큰 수를 찾기 위해 크기 N인 최소 힙(min-heap)을 유지한다. 힙에는 항상 지금까지 본 수 중 상위 N개가 저장되고, 힙의 최솟값이 곧 N번째 큰 수가 된다.
- 첫 행 초기화: 첫 번째 행의 N개 값을 모두 최소 힙에 삽입한다.
- 나머지 행 처리: 2행부터 N행까지 각 원소를 확인한다. 현재 원소가 힙의 최솟값(
pq.peek())보다 크면, 최솟값을 제거하고 현재 원소를 삽입한다. 이렇게 하면 힙 크기가 항상 N으로 유지된다. - 결과 반환: 모든 행을 처리한 후 힙의 최솟값(
pq.peek())이 전체 N²개 수 중 N번째로 큰 값이다. - 메모리 절약: N×N 전체를 저장하지 않고 크기 N인 힙만 유지하므로 O(N) 공간만 사용한다.
코드
package ASP_study.day299;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Day298BOJ2075N번째큰수 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int n = Integer.parseInt(br.readLine());
PriorityQueue<Integer> pq = new PriorityQueue<>();
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
pq.add(Integer.parseInt(st.nextToken()));
}
for (int i = 1; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int num = Integer.parseInt(st.nextToken());
if (pq.peek() < num) {
pq.poll();
pq.offer(num);
}
}
}
System.out.println(pq.peek());
}
}복잡도
- 시간: O(N² log N) — N²개의 원소를 순회하며 각 힙 연산 O(log N)
- 공간: O(N) — 크기 N인 최소 힙