피곤🤢

문제링크

백준 #2075. N번째 큰 수

풀이방법

음 일단 이 문제의 "모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것" 조건을 다음과 같이 생각했다.
1. 위 숫자들은 아래 숫자보다 작음-> 필요시에만 비교하자
2. 가장 밑에 있는 숫자들은 각 라인의 가장 큰 수 -> 여기서 가장 크면 모든 숫자 중 최대값
== 가장 큰 수 하나를 빼고 각 라인의 가장 큰 수를 선택 -> 여기서 가장 큰 수는 모든 숫자 중 두번째로 큰 수

따라서, 각 열의 가장 큰 수 중 가장 큰 수를 뽑아내고 해당 열에서 다음으로 큰 수를 채워넣어 비교를 하는 방식으로 문제를 해결했다.

문제 해결 시 사용한 자료구조는 우선순위큐인데, 삽입 연산이 자주 일어나고 가장 큰 수를 뽑아 내는(반정렬상태이기때문에!) 문제에 적합하다고 생각했기 때문이다.

코드

import java.util.PriorityQueue;
import java.util.Scanner;

public class NthNumber {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int[][] array = new int[n][n];
        for (int y = 0; y < n; y++) {
            for (int x = 0; x < n; x++) array[y][x] = sc.nextInt();
        }

        PriorityQueue<ValueInfo> queue = new PriorityQueue();
        for (int i = 0; i < n; i++) queue.add(new ValueInfo(n - 1, i, array[n - 1][i]));

        int max = 0;
        for (int i = 0; i < n; i++) {
            ValueInfo head = queue.poll();
            max = head.value;

            if ((head.y - 1) >= 0) queue.add(new ValueInfo(head.y - 1, head.x, array[head.y - 1][head.x]));
        }

        System.out.print(max);
    }
}

class ValueInfo implements Comparable<ValueInfo> {
    public int y;
    public int x;
    public int value;

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

    @Override
    public int compareTo(ValueInfo o) {
        return o.value - this.value;
    }
}

🙇🏻‍♀️