Algorithm/BaekJoon

[2075 N번째 큰 수]

돌건 2021. 4. 6. 23:07
 

2075번: N번째 큰 수

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

www.acmicpc.net

 

  • 분석 및 해결

처음에 봤을 때는 뭔가 대단한 수학적 사고를 요하는 것 같았지만, 우선순위 큐를 이용해 쉽게 풀 수 있었다. 2차원 배열의 모든 원소를 우선순위 큐에 삽입하고, N번만큼 뽑아내면 된다.

 

  • 소스 코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class BJ_2075 {

	private static int N;
	private static PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		
		for(int iter = 0; iter < N; iter++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			while(st.hasMoreTokens()) {
				pq.offer(Integer.parseInt(st.nextToken()));
			}
		}
		
		int answer = 0;
		for(int iter = 0; iter < N; iter++) {
			answer = pq.poll();
		}
		
		System.out.println(answer);
	}

}