백준 11279 최대 힙 Java

힙 자료구조를 사용해야 하는 최대 힙 문제이다

 

문제의 내용은 2가지 연산을 지원하는데

0인 경우엔 최대힙에서 가장 윗부분 가장 큰 수를 삭제 후 출력

0이 아닌 경우엔 최대힙에 삽입하는 것이다.

 

힙 정렬을 배웠지만

힙 정렬은 삽입 없이 삭제 후 다시 힙으로 만들어 주는 과정을 반복하지

삽입과 삭제를 따로 구현하지 않아서

힙에서 삽입과 삭제를 따로 구현하려니까

생각대로 잘 안됐다.

 

코드를 천천히 살펴보면서 꼭 복습해보자.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Q11279 {
    public static int [] heap = new int[100001];
    public static int size = 0;
    public static StringBuilder sb = new StringBuilder();
 
    public static void swap(int x, int y) {
        int temp = heap[x];
        heap[x] = heap[y];
        heap[y] = temp;
    }
    public static void push(int x) {
        heap[++size] = x;
        //삽입한 것 부터 힙인지 확인, 힙이아니면 계속 부모노드로 올라가고 힙이면 break
        for(int i=size; i>1; i/=2) {
            if(heap[i/2] < heap[i]) {
                swap(i/2, i);
            } else {
                break;
            }
        }
    }
 
    public static void pop() {
        sb.append(heap[1]+"\n");
        heap[1] = heap[size];
        heap[size--] = 0;
        for(int i=1; i*2<=size;) { //삭제 후 1에서 부터 힙으로 만들어주는 과정
            if(heap[i] > heap[i*2] && heap[i] > heap[i*2+1]) {
                break;
            }else if(heap[i*2] > heap[i*2+1]) {
                swap(i, i*2);
                i = i*2;
            } else {
                swap(i, i*2+1);
                i = i*2+1;
            }
        }
    }
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        for(int i=0; i<n; i++) {
            int k = Integer.parseInt(reader.readLine());
            if(k==0) {
                if(size == 0) {
                    sb.append(0+"\n");
                } else {
                    pop();
                }
            } else {
                push(k);
            }
        }
        System.out.print(sb.toString());
    }
}

이 문제를 힙을 구현하지 않고도 해결할 수 있는 방법이 있는데

바로 PriorityQueue(우선순위 큐)이다.

PriorityQueue는 삭제 연산을 했을 때 우선순위가 가장 높은 것을 우선으로 삭제한다.

자바에서는 라이브러리에 있는 우선순위 큐를 특별한 설정 없이 사용했을 때

최소 힙처럼 최솟값을 우선으로 삭제한다.

이 문제에서는 최댓값을 삭제 후 출력해줘야 하므로

우선순위 큐에 삽입시에 -1을 곱해서 음수 형태로 삽입시켜줌으로써

최댓값이 우선순위가 가장 높게 해주고

삭제 시에 삭제된 값에 -1을 곱해서 출력하면 양수 형태로 출력되게 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
 
public class Q11279_ver2 {
 
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        Queue<Integer> q = new PriorityQueue<>();
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<n; i++) {
            
            int k = Integer.parseInt(reader.readLine());
            if(k==0) {
                if(q.isEmpty()) {
                    sb.append(0+"\n");
                } else {
                    //출력할 땐 다시 -1을 곱해서 양수로 
                    sb.append(q.poll()*-1+"\n");
                }
            } else {
                //최댓값을 삭제해야 하므로 삽입 시 -1을 곱해준다.
                q.add(k*-1);
            }
        }
        System.out.print(sb.toString());
    }
}