문제

백준 2075번
https://www.acmicpc.net/problem/2075

N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.

이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

첫째 줄에 N번째 큰 수를 출력한다.

• 예시
  

  • 총 N × N 의 값의 갯수 중 N번 째로 큰 숫자를 반환하면 되는 것이다.
  • N × N번 만큼 for문 값 전부 비교해서 N번 째로 큰 값을 찾는 것이 아니라 전부 돌지 않고 푸는 방법을 고민했다.
  • 그리고 모든 값들이 빨간색 화살표처럼 같은 열에 있는 (현재 행 - 1)보다 큰 수라는 것을 이용했다.

Code

• 먼저 행과 열, 그리고 값 그리고 Comparable interface를 통해 내림차순으로 정렬을 할 class 생성
• int[][] 배열에 들어갈 N × N의 값을 넣어준다.
• (N - 1)번 째 행의 값이 (N - 2)번 째 값들보다 크기 때문에 우선순위 큐에 (N - 1)번 째 값들만 먼저 넣어준다.
• 그리고 우선순위 큐에 들어 있는 N개의 값 중 MAX 값을 우선순위 큐에서 빼주고 MAX였던 값 바로 위의 값을 다시 우선순위 큐에 넣어준다.
• 처음에 우선순위 큐에 N개를 넣었기 때문에 (N - 1)번의 for문을 통해 N번 째로 큰 값을 peek()로 반환한다.

Java

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

class Point implements Comparable<Point> {
    int x; // 행
    int y; // 열
    int value; // 값

    public Point(int x, int y, int value) {
        this.x = x;
        this.y = y;
        this.value = value;
    }

    @Override
    public int compareTo(Point o) {
        return o.value - this.value; // 내림차순
    }
}
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());

        int[][] arr = new int[N][N]; // N × N 배열
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        PriorityQueue<Point> pq = new PriorityQueue<>(); // 우선순위 큐
        for (int i = 0; i < N; i++) {
        	// 마지막 행에 있는 값들 넣어주는 경우
            pq.offer(new Point(N - 1, i, arr[N - 1][i]));
        }


        int x, y;
        for (int i = 0; i < N - 1; i++) {
            Point max = pq.poll();
            x = max.x; // max의 행 값
            y = max.y; // max의 열 값

            if (x - 1 >= 0) {
            	// 우선순위 큐에서 max을 값을 빼고 그 max 값 바로 위의 값을 넣는 조건
                pq.offer(new Point(x - 1, y, arr[x - 1][y]));
            }

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