[BOJ 2075] N번째 큰 수 (S3)

 

📍 문제

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

 

 

 

📍 문제 풀이

수를 입력받고 N번째 큰 수를 구해야하기 때문에 정렬이 필요하다

 

기본적으로 N*N 크기의 배열을 정렬해서 답을 구할 수 있지만

시간을 줄이기 위해서 우선순위 큐를 사용할 수 있다. 

 

기본적으로 오름차순, 내림차순 뿐만 아니라 직접 정렬 조건을 설정할 수 있다.

이 문제의 경우에는 N번째 큰 수를 구해야하기 때문에 

오름차순 보다는 내림차순이 그럴듯한 정렬 기준이다. 

 

우선순위 큐의 정렬과 관련된 정리는 여기에..

📍 전체 코드

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

public class boj_2075 {
	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<>(Collections.reverseOrder());
		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()));
			}
		}

		int idx = 0;
		while (true) {
			if (idx == n - 1) {
				System.out.println(pq.poll());
				return;
			}
			pq.poll();
			idx++;
		}

	}
}