[Java] BOJ 11279 최대 힙

문제 

문제 링크 https://www.acmicpc.net/problem/11279

• 널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
  1. 배열에 자연수 x를 넣는다.
  2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
• 프로그램은 처음에 비어있는 배열에서 시작하게 된다.
• 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
• 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다.
• 입력되는 자연수는 231보다 작다.
• 입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

아이디어

• PriorityQueue를 사용하여 heap을 구현했다.
• 기본 heap은 우선순위가 낮은 것이 제일 위에 오므로 반대로 정렬하면 우선순위가 높은 것이 제일 위에 온다.

겪은 시행착오

• X

최소 힙과 비슷하게 풀면돼서 좋았다...!

 

코드

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

public class BOJ11279 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        // 컬렉션에 데이터를 넣으면 remove되는 peek의 값이 minHeap의 최솟값이 됨
        // Primary Queue는 우선순위 큐로 우선순위가 가장 낮은 값이 먼저 나오게 되어있음
        // 우선순위가 낮다는 것은 Integer를 넣었을 때, 최솟값으로 판단됨
        // 따라서 반대로 정렬하면 최대힙이 되어 최댓값을 출력함
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

        // 연산의 개수
        int N = Integer.parseInt(br.readLine());

        // 연산의 개수만큼 반복
        for(int i = 0; i < N; i++){
            int x = Integer.parseInt(br.readLine());

            // 만약 입력받은 수가 0일때
            if(x == 0){
                // maxHeap이 비어있다면
                if(maxHeap.isEmpty()){
                    // 0을 출력
                    sb.append(0 + "\n");
                }
                // 만약 maxHeap이 비어있지 않다면
                else{
                    // maxHeap의 꼭대기 값을 출력하고
                    sb.append(maxHeap.peek() + "\n");

                    // maxHeap의 맨 위의 값을 제거
                    maxHeap.poll();
                }
            }
            // 만약 입력받은 수가 0이 아니라면
            else{
                // maxHeap에 x를 추가
                maxHeap.add(x);
            }
        }

        System.out.println(sb);
        
    }
}