[백준/자바] 11279번: 최대 힙

문제

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

풀이

• 최대 힙을 이용하여 다음 연산을 지원하는 프로그램 작성

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

최소 힙이 아닌 최대 힙을 구현하는 문제입니다.
자연수를 입력 받았을 경우 값을 추가하고 0을 입력 받았을 때 pop 해주면 됩니다.

저는 최대 힙을 어떻게 구현할까 고민하던 와중 최소 힙의 성질을 거꾸로 이용하면 좋을 것 같아 다음과 같은 방식으로 구현했습니다.

		PriorityQueue<Integer> pq = new PriorityQueue<>(); // 최소 힙
		for (int i = 0; i < n; i++) {
			int x = Integer.parseInt(br.readLine());
			switch (x) {
			case 0: // 0일 경우
				if (pq.isEmpty()) { // 큐가 비었을 경우 0 출력
					sb.append(0).append('\n');
				} else { // 아닐 경우 최댓값 출력
					sb.append(-pq.poll()).append('\n');
				}
				break;
			default: // 자연수일 경우
				pq.add(-x); // 큐에 추가
			}
		}

• 값을 입력 받을 때 음수로 받는 것입니다.
• 최소 힙일 경우엔 가장 작은 값부터 출력하는 성질을 이용했습니다.
• 입력 받은 값을 음수로 받게 되면, 출력할 때 가장 작은 값을 출력하므로 절댓값이 가장 큰 수가 출력되므로 매우 간편하게 최대 힙을 구현할 수 있습니다.
• 큐를 만들 때, new PriorityQueue<>(Collections.reverseOrder());로 선언하면 최대 힙을 구현할 수도 있습니다.
• 그러나 시간복잡도를 고려하면 음수로 바꾸어 넣는 것이 더 효율적입니다.

코드

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

public class Main_11279 {
	static StringBuilder sb = new StringBuilder();
	
	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<>();
		for (int i = 0; i < n; i++) {
			int x = Integer.parseInt(br.readLine());
			switch (x) {
			case 0:
				if (pq.isEmpty()) {
					sb.append(0).append('\n');
				} else {
					sb.append(-pq.poll()).append('\n');
				}
				break;
			default:
				pq.add(-x);
			}
		}
		
		System.out.println(sb.toString());
	}

}