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

문제

 

 

접근 방식

배열에 수를 모두 저장한 후에 정렬하고 끝에서 n번째 인덱스를 출력해도 풀리는 문제지만

우선순위 큐를 이용해서 좀 더 효율적으로 풀 수 있다.

 

최소 힙으로도 풀 수 있지만 최대 힙으로 푸는 것이 더 효율적이니

자바에서 제공하는 우선순위 큐 기준으로는 생성자 파라미터로 정렬 기준을

역순으로 주어 최대 힙을 사용할 수 있다.

 

최대 힙에 입력 받은 수들을 모두 넣어준 후에

n개를 꺼내면 n번째 큰 수가 나오게 된다.

 

풀이

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 nNum = 0;

		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()));
			}
		}

		while (n-- > 0) {
			nNum = pq.poll();
		}

		System.out.println(nNum);
	}
}