[백준] 2075 N번째 큰 수 -Java / Python

 

 

 

그냥 배열을 생성해서 sort로 정렬해준 뒤 인덱스에 맞춰서 출력해줘도 시간 초과가 나오지 않는다.

 

그래도 우선순위 큐와 슬라이싱 윈도우 알고리즘을 활용해서 좀 더 효율적으로 풀어보자.

 

Java

 

일단 우선순위 큐만 사용했을 때 풀이이다.

 

import java.util.*;
import java.io.*;

class Main {
  public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;

      int N = Integer.parseInt(br.readLine());

      PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
      
      for(int i=0; i<N; i++){
        st = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<N; j++){
          pq.offer(Integer.parseInt(st.nextToken()));
        }
      }

      for(int i=0; i<N-1; i++){
        pq.poll();
      }

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


      

       
    }
}

 

다음으로 우선순위 큐와 슬라이싱 윈도우 알고리즘을 사용한 풀이이다.

우선순위 큐의 사이즈가 N일때는 더 이상 사이즈를 늘리지 않고, 입력받는 수와 비교해서 더 큰 수를 입력받을 때만 N번째 위치에 있는 수를 바꿔준다.

 

import java.util.*;
import java.io.*;

class Main {
  public static void main(String[] args) throws Exception {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st;

      int N = Integer.parseInt(br.readLine());

      PriorityQueue<Integer> pq = new PriorityQueue<>();
      
      for(int i=0; i<N; i++){
        st = new StringTokenizer(br.readLine(), " ");
        for(int j=0; j<N; j++){
          int temp = Integer.parseInt(st.nextToken());
          if(pq.size() == N){
            if(pq.peek() < temp){
              pq.poll();
              pq.add(temp);
            }
          }else{
            pq.add(temp);
          }
        }
      }

   
   

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


      

       
    }
}

 

 

Python

 

파이썬도 자바와 비슷하게 풀었다.

원소 N개를 유지하면서 최솟값을 버리는 방식으로 구현했다.

 

import sys
input = sys.stdin.readline
import heapq

N = int(input())

pq = []

for i in range(N):
  temp = list(map(int, input().split(" ")))

  if not pq: # 비어있으면 넣어 줌
    for j in temp:
      heapq.heappush(pq, j) 
  else: # 사이즈가 N이면 하나씩 조절
    for j in temp:
      heapq.heappush(pq,j)
      heapq.heappop(pq)

print(pq[0])