[ BOJ 2075 ] N번째 큰 수 ( JAVA )

N번째 큰 수 

문제

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

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

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

입력

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

출력

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	12 MB	22578	9076	6519	39.148%

---

구현

- N번째 큰 수를 찾는 문제입니다. 가장 큰 수부터 하나씩 제거하며 N번째로 큰 수를 찾도록 구현하였습니다.

각 열마다 정렬이 되어있으므로 각 열의 가장 마지막 행에 있는 수들을 최대힙에 넣고 하나씩 꺼내면서 꺼낼때마다 그 수의 바로 위의 행의 수(같은 열중에 자신보다 바로 하나 작은 수)를 다시 최대힙에 추가하는 방식으로 구현했습니다.

(해보지는 않았지만 하나씩 넣지 않고 모든 수 (최대 1500 * 1500개의 수)를 전부 힙에 넣으면 아마 메모리 제한에 걸릴 것 같습니다.)

 

제출 결과

---

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

/**
 * N번째 큰 수
 */
public class BOJ2075 {

    static int n;
    static int map[][];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PriorityQueue<Info> pq = new PriorityQueue<>((i1,i2) -> i2.num - i1.num);

        n = Integer.parseInt(br.readLine());

        map = new int[n + 1][n + 1];

        for (int i = 1; i <= n; i++) {
            String s[] = br.readLine().split(" ");
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(s[j - 1]);
                if (i == n) pq.add(new Info(i, j, map[i][j]));
            }
        }

        for (int i = 0; i < n - 1; i++) {
            Info max = pq.poll();
            if(max.x > 1)
                pq.add(new Info(max.x - 1, max.y, map[max.x - 1][max.y]));
        }

        System.out.println(pq.poll().num);
    }

    static class Info{
        int x, y, num;

        public Info(int x, int y, int num) {
            this.x = x;
            this.y = y;
            this.num = num;
        }
    }
}

---

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

2075번: N번째 큰 수

---