Baekjoon 2075 N번째 큰 수 JAVA

2075번: 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번째 큰 수를 출력한다.

 

풀이

해당 문제는 2차원 배열에 숫자가 주어졌을 때 N번째 큰 수를 출력하는 문제다.

우선순위 큐를 이용하여 해결했으며 우선순위 로직은 아래와 같다.

 

1. 먼저 우선순위 큐를 선언함과 동시에 람다식으로 내림차순 정렬을 한다.

2. 입력값을 큐에 넣어준다.

3. N-1의 크기만큼 큐에서 값을 빼낸다.

4. 큐에서 값을 빼내서 출력한다.

 

코드

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

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> pq = new PriorityQueue<>((a,b) -> b - a); // 우선순위 큐를 내림차순으로 람다식으로 정렬한다.

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) { // 우선순위 큐에 숫자를 모두 넣어준다.
                pq.add(Integer.parseInt(st.nextToken()));
            }
        }

        for (int i = 0; i < N-1; i++) { // 이전값만큼은 빼내고 
            pq.poll();
        }
        System.out.println(pq.poll()); // 출력값 출력
    }
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드