[백준] N번째 큰 (2075) - Java

문제

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 

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

예제 출력 1 

35

 

 

내가 푼 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        PriorityQueue<Integer> queue = new PriorityQueue<>();   // 오름차순정렬 (작은수가 맨 앞 )

        for (int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());    // 12 7 9 15 5
            for (int j=0; j<N; j++) {
                if (queue.size() < N)
                    queue.offer(Integer.parseInt(st.nextToken()));
                else {
                    queue.offer(Integer.parseInt(st.nextToken()));
                    queue.poll();
                }
            }

        }

        System.out.println(queue.poll());
    }
}

N = 5라면 총 25개의 숫자들 중 5번째로 큰수를 찾아야한다.

25개의 숫자를 모두 비교해야하기때문에 배열에 넣고 sort() 하는것 보다는 우선순위큐를 사용하면 된다.

 

우선순위큐는 기본적으로 오른차순 정렬로 되어있기 때문에 큐에 숫자를 N개만 유지하면서 값을 하나씩 넣고 제일 작은수를 poll() 해주면 25개의 숫자 중 큰 수 5개만 큐에 남게된다.

이때, 오름차순되어 있기 때문에 poll()하면 맨 앞에 있는 숫자가 5개 중 가장 작은 수가 되고 그게 25개의 숫자 중 5번째로 큰 수가 된다.