BJ2075 : N번째 큰 수

 

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

---

접근 방법

• 가볍게 풀 수 있는 문제인가 싶었지만 기본 배열로는 풀 수가 없다.
• 함께 공부하는 동료의 조언으로 우선순위 큐를 시도하였다.
• 우선순위 큐를 활용하여 풀면 시간복잡도가 유리하여 편리하게 풀 수 있다.
• 참조링크

👉 우선순위 큐의 시간 복잡도
우선순위 큐는 완전 이진트리 형태의 힙을 이용해 구현할 수 있다.
우선순위 큐의 삽입과 삭제는 𝑂(𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다.
우선순위 큐를 이용한 정렬은 𝑂(𝑁𝑙𝑜𝑔𝑁)의 시간 복잡도를 가진다

 

풀이

• 메모리 273980 KB / 836 ms

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 = new StringTokenizer(br.readLine());
        
        int n = Integer.parseInt(st.nextToken());
        
        PriorityQueue<Integer> q = new PriorityQueue(Collections.reverseOrder());
        
        for (int i=0; i<n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j=0; j<n; j++) {
                q.add(Integer.parseInt(st.nextToken()));
            }
        }
        
        int answer = 0;
        
        for (int k=0; k<n; k++) {
            answer = q.poll();
        }
        
        System.out.println(answer);
    }
}