[백준] 2075 N번째 큰 수 java 풀이 (풀이 2개)

1. 문제 설명

문제 링크

2. 접근 방식

key word: Priority Queue

N*N개의 수 중 N 번째 큰 수를 구하는 것이다.
그래서 나는 오름 차순 PriorityQueue를 만들어서 해당 queue의 size를 N개로 유지한다. 방법은 다음과 같다.

1. 맨 마지막 행의 값 N개를 PQ에 담는다. (맨 마지막 행은 각 열 별로 최고값 이다.)
2. 배열을 한 행씩 올라가서 값들을 Priority Queue의 peek()값과 비교한다.
   (1) peek() < 현 조회 중인 값: peek()을 poll() 해서 버리고, 현 조회중인 값을 PQ에 넣는다.
   (2) peek() >= 현 조회 중인 값: PQ를 N개로 유지하는 이유는 N번째 큰수를 찾기 위해서 이다. 현재도 PQ 안의 최소값보다 작으므로 N번째 큰 수가 되기 만무하다. 그냥 넘어간다.
3. 이런 식으로 하면 PQ.peek()은 N번째 큰 수가 담기므로, 그 수를 출력한다.

3. 코드 분석

import java.io.*;
import java.nio.Buffer;
import java.util.*;

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());
        int [][] arr = new int [N][N];

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

        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            pq.add(arr[N-1][i]);
        }

        for(int i = N-2; i>=0; i--){
            for(int j = 0; j< N; j++){
                if(pq.peek() < arr[i][j]) {
                    pq.poll();
                    pq.add(arr[i][j]);
                }
            }
        }

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

4. 성장 하기

다른 사람의 풀이를 보니 저 방식 보다 쉬운 방식이 있었다.

1. PQ의 정렬 기준을 내림 차순으로 한다.
2. PQ에 모든 값을 넣는다.
3. N-1개를 poll() 한다.

그러면 PQ.peek()이 N번째 큰 수가 된다. 풀이는 다음과 같다.

import java.io.*;
import java.nio.Buffer;
import java.util.*;

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> pq = new PriorityQueue<>((o1,o2) -> o2 - o1);

        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.peek());
    }
}