[백준] 2075번 N번째 큰 수 Java

N번째 큰 수

간단하게 list에 모두 넣고 sort한 다음 n번째 큰 수를 꺼내는 방법과 우선순위 큐를 사용하여 n개의 큐를 유지시키며 최소값인 큐의 마지막 숫자를 빼내는 풀이 방법이 있습니다.

시간차이는 두 배정도 우선순위 큐가 빠릅니다.

큐는 선입선출 FIFO의 특징을 가지고 있습니다.

우선순위 큐는 먼저 들어오는 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가게 됩니다.

디폴트는 우선순위가 낮은 숫자 순 입니다.

PriorityQueue priorityQueue = new PriorityQueue<>();

---

List 풀이 방법

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;
      int n = Integer.parseInt(br.readLine());

      int[] list = new int[n*n];
      int idx = 0;

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

      Arrays.sort(list);
      System.out.println(list[n*n - n]);
  }
}

PrioityQueue 풀이 방법

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;

      PriorityQueue<Integer> queue = new PriorityQueue<>();
      int n = Integer.parseInt(br.readLine());

      //첫번째 줄 n개의 Queue 생성
      st = new StringTokenizer(br.readLine());
      for (int i = 0; i < n; i++) {
          queue.offer(Integer.parseInt(st.nextToken()));
      }
      
      //Queue n개 유지하며 입력값 넣기
      for (int i = 1; i < n; i++) {
          st = new StringTokenizer(br.readLine());
          for (int j = 0; j < n; j++) {
              Integer tmp = Integer.parseInt(st.nextToken());
              //Queue 마지막 값과 비교하여 더 클 때만 넣기
              if(tmp > queue.peek()){
                  queue.poll();
                  queue.offer(tmp);
              }
          }
      }
      System.out.println(queue.poll());
  }
}