[Java] 백준(실버-2) 11279번 - 최대 힙

문제 풀이

---

이 문제는 주어진대로 최대 힙을 우선순위 큐를 이용해 구현하면 되는 간단한 문제이다.

아이디어 도출

우선순위 큐를 이용했던 이전 문제 최소 힙과 동일한 풀이 방법으로 풀 수 있다.

최소 힙은 PriorityQueue의 기본 값으로 설정되어 있어 그냥 선언만 해도 최소 힙을 구현할 수 있었으나 최대 힙의 경우 추가적인 설정이 필요하다. 필자가 최대 힙을 구하기 위해 설정한 방법은 2가지이다.

1. Collections 패키지의 reverseOrder() 메소드 이용하기
2. Comparator 클래스를 상속받아 compare() 메소드 오버라이딩하기

2가지 방법 모두 우선순위 큐의 우선순위를 높은 순으로 설정할 수 있는 방법들이니 자유롭게 원하는 것을 선택하여 풀면 된다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {    

    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // Collections 패키지의 reverseOrder() 메소드로 우선순위를 높은 순으로 설정할 수 있다.
        // PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        
        // Comparator 클래스를 상속받아 compare() 메소드를 오버라이딩하여 우선순위를 높은 순으로 설정한다.
        PriorityQueue<Integer> q = new PriorityQueue<>(new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                if(o1 > o2) {
                    return -1;
                }
                else if(o1 < o2) {
                    return 1;
                }
                else {
                    return 0;
                }
            }
            
        });

        int N = Integer.parseInt(br.readLine());

        for(int i=0; i<N; i++) {
            int num = Integer.parseInt(br.readLine());
            
            // 만약 입력값이 0보다 큰 자연수라면 우선순위 큐에 삽입.
            if(num > 0) {
                q.offer(num);
                continue;
            }

            // 0일 때 우선순위 큐가 비어있다면 0을, 비어있지 않다면 가장 높은 수를 꺼낸다.
            if(!q.isEmpty()) {
                bw.write(q.poll()+"\n");
            } else {
                bw.write("0"+"\n");
            }
            
        }
        
        bw.close();
        br.close();
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.