백준1927_최소힙

문제

널리 잘 알려진 자료구조 중 최소 힙이라는 것이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

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

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 

9
0
12345678
1
2
0
0
0
0
32

예제 출력 

0
1
2
12345678
0

[코드]

import java.util.Arrays;
import java.util.Scanner;
 
public class B1927_minHeap {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
 
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 전체 개수
        Heap h = new Heap(N);
        int Heap[] = new int[N];
        int out = 0;
 
        for (int i = 0; i < N; i++) {
            int num = sc.nextInt();
            if (num == 0)
                System.out.println(h.removeNode());
            else
                h.addNode(num);
        }
    }
}
 
class Heap {
    int heap[];
    int size = 0;
 
    public Heap(int n) {
        heap = new int[n];
    }
 
    public void addNode(int newInt) {
        //마지막에 먼저 넣고, 걔를 자식 노드랑 같이 비교하기
        int p;
        heap[size] = newInt;
        p = size;
        size++;
        while (p > 0 && heap[p] < heap[(p - 1) / 2]) {
            int temp = heap[p]; 
            heap[p] = heap[(p - 1) / 2];
            heap[(p - 1) / 2] = temp;
            p = (p - 1) / 2;
        }
    }
 
    public boolean isEmpty() {
        if (size == 0)
            return true;
        else
            return false;
    }
 
    public int removeNode() {
 
        int rst;
        if (!isEmpty()) {
            rst = heap[0];
            heap[0] = heap[--size];
            heap[size] = 0;
        } else {
            return 0;
        }
 
        arrange();
 
        return rst;
    }
 
    public void arrange() {
        int p = 0; // 루트 노드에서 부터 크기 비교 후 swap 해준다.
    
        while (p * 2 + 1 < size-1) {
            if (heap[p * 2 + 1] > heap[p * 2 + 2]) {
                int temp = heap[p];
                heap[p] = heap[p * 2 + 1];
                heap[p * 2 + 1] = temp;
                p = p * 2 + 1;
            } else {
                int temp = heap[p];
                heap[p] = heap[p * 2 + 2];
                heap[p * 2 + 2] = temp;
                p = p * 2 + 2;
            }
        }
    }
}

힙을 처음 배워봐서 인터넷에서 좀 참고해서 짜봤는데도

틀렸다고 계속 뜬다 ㅜ_ㅜ

그래도 일단은... 중간기록 ㅠㅠ