[Java][백준] #11279 - 최대 힙

🔗 백준 11279 - 최대 힙

문제

알고리즘 분류

• 자료 구조
• 우선 순위 큐

---

우선 순위 큐(Prirority Queue)란?

• FIFO형태로 데이터가 출입되는 일반 큐와 달리, 우선순위에 따라 데이터가 출입되는 큐이다.
• 기본형은 작은 숫자부터(내림차순) 우선순위를 가지며, Collections.reverseOrder() 메소드를 이용해 오름차순으로 우선순위를 지정할 수 있다.
  🔗 참고자료 - 우선 순위 큐

풀이

1. 우선 순위 큐 선언

• reverseOrder() 메소드를 이용해 오름차순(큰 숫자부터) 우선순위 지정

        Queue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());

2. x에 따른 연산

        for(int i = 0; i<n; i++){
            int x = Integer.parseInt(br.readLine());
            if (x > 0){ //자연수일 경우
                heap.add(x);
            } else if (x == 0){ //0일 경우
                Integer polled = heap.poll();
                if(polled == null){ //배열이 비어있을 경우
                    sb.append(0 + "\n");
                }else
                    sb.append(polled + "\n");
            }
        }

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Queue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<n; i++){
            int x = Integer.parseInt(br.readLine());
            if (x > 0){
                heap.add(x);
            } else if (x == 0){
                Integer polled = heap.poll();
                if(polled == null){
                    sb.append(0 + "\n");
                }else
                    sb.append(polled + "\n");
            }
        }
        System.out.println(sb);
    }
}