11279번

https://www.acmicpc.net/problem/11279

11279번: 최대 힙

먼저 이문제는 자료구조 중에 힙을 이용한 것이고 우선순위 큐 형태이다. 그래서 아주 간단하게는 자바에서 제공하는 PriorityQueue를 사용해서 푸는 방법이 있다. 하지만 힙의 구조와 우선순위 큐에 대해 알아보기 위해서 직접 힙을 구현해봤다.

 

아래의 블로그글을 참고하여 거의 똑같이 구성하였다.

https://st-lab.tistory.com/219

자바 [JAVA] - Priority Queue (우선순위 큐) 구현하기

정말 설명을 너무 잘하시는 분이라서 자바를 사용하는 사람이라면 누구나 한번쯤은 이분글을 봤을 거라고 생각한다.

 

그래서 원리는 위의 글을 읽는 걸 추천하지만 간단하게 설명하겠다.

먼저 우선순위 큐의 형태는 약한 힙, 불완전 이진트리라고 생각할 수 있다. 비교기준에 따라서 숫자를 트리구조로 구성하는 방식인데

위의 문제는 최대 힙 문제이기 때문에 이를 예로 들겠다.

최대 힙의 경우 루트 노드를 기준으로 자식 노드들을 루트 노드보다 작은 값들로 구성하는 형태이다. 아래의 그림과 같은 형태라고 생각하면 된다.

 

그렇다면 여기서 3이라는 값이 추가된다고 생각해보자

3을 추가 한다면, 제일 밑인 7아래에 3이 붙을 것이다.

그 이유는 아래의 조건을 생각하면 된다.

- 왼쪽 자식노드의 인덱스 = 부모 노드*2

- 오른쪽 자식노드의 인덱스 = 부모 노드*2+1

- 부모 노드 = 자식노드/2

그럼 값이 들어왔을 때 배열의 마지막에 값이 추가되기 때문에 추가된 값과 부모 노드의 값을 비교해서 자식 노드가 부모 노드보다 크다면 자식 노드와 자리를 바꾸는 것이다. 이걸 자식노드의 인덱스값이 1보다 클때까지 반복한다. 그 이유는 루트 노드의 인덱스를 1로 지정했기 때문에 비교노드가 만약 제일 큰 값이라면 루트 노드와의 비교는 비교 노드의 인덱스 값이 2일때 이루어지기 때문이다.

 

그렇게 트리를 완성했다면 이제는 0이라는 출력 명령어가 나왔을 때 루트 노드를 뽑아내기 위한 offer메서드를 정의해야한다.

힙에서 값을 빼내는 원리는 루트노드를 빼내고 제일 아래에 있는 자식 노드를 루트노드로 옮겨서 그 값을 비교하여 다시 정렬하는 것이다.

위의 그림을 예로 들어보자면 10을 빼내었다고 했을 때, 제일 아래에 있는 4를 루트 노드로 지정한다.

그런다음 9와 8중에 큰값과 4를 비교한다 그 이유는 루트 노드의 값은 제일 큰값이 되어야하기 때문이다. 따라서 9와 4를 비교하여 9와 4의 자리를 바꾼다.

그다음 7과 6중에 7이 더 큼으로 4와 비교하여 7과 4의 자리를 바꾼다. 그러면 다시 정렬이 이루어진다.

정리하자면 부모노드와 두 자식노드 중에 큰값을 비교하여 부모노드와 자식노드의 자리를 부모노드가 자식노드보다 클때까지 바꾸는 것을 반복하는 것이다. 

 

그래서 코드를 작성하면 아래와 같다.

package backjoon;


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

public class b11279 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int count = Integer.parseInt(br.readLine());
        //PriorityQueue<Integer> arr = new PriorityQueue<>(Collections.reverseOrder());
        StringBuilder sb = new StringBuilder();
        heap h = new heap(count);
        for(int i=0; i<count; i++){
            int tmp = Integer.parseInt(br.readLine());
            if(tmp==0){
                if(h.isEmpty()){
                    sb.append(0).append("\n");
                }
                else {
                    sb.append(h.poll()).append("\n");
                }
            }
            else {
                h.offer(tmp);
            }
        }
        System.out.println(sb);
    }
}
class heap{
    public int getParent(int index){
        return index/2;
    }
    public int getLeftChild(int index){
        return index*2;
    }
    public int getRightChild(int index){
        return index*2+1;
    }
    public boolean isEmpty(){
        return size==0;
    }
    int size;
    int[] arr;
    public heap(int size){
        this.arr=new int[size];
        this.size=0;
    }
    public void offer(int value){
        shiftUp(size+1,value);//마지막 노드의 뒤에 붙은 비교값의 인덱스와 비교값을 전달
        size++;//전체 트리의 크기가 증가했음
    }
    public void shiftUp(int index, int target){
        while (index>1){
            int parent = getParent(index);
            int parentVal = arr[parent];

            if(target<=parentVal){
                break;
            }
            arr[index] = parentVal;
            index=parent;
        }
        arr[index]=target;
    }//부모와 비교값을 비교하여 비교값이 크면 부모 노드와 자리를 바꿈, 비교노드가 부모노드보다 작을 때까지 반복

    public int poll() {

        if (size == 0) {
            return 0;
        }
        int result = arr[1];
        int target = arr[size];
        arr[size] = 0;
        size--;
        siftDown(1,target);
        return result;
    }//뽑아낸 루트노드를 출력하고, 트리를 다시정렬한다. 결과는 원래의 루트노드, 타겟은 맨마지막 자식 노드
    public void siftDown(int index, int target){
        arr[index]=0;
        int parent = index;
        int child;
        while((child=getLeftChild(parent))<=size){

                int right = getRightChild(parent);
                int childVal = arr[child];

                if(arr[right]>childVal && right<=size){
                    child = right;
                    childVal = arr[child];
                }
                if(target>=childVal){
                    break;
                }
                arr[parent]=childVal;
                parent=child;
            }
        	arr[parent]=target;
        }//왼쪽의 자식노드를 기준으로 오른쪽 자식노드가 크면 비교할 자식노드를 오른쪽으로 바꾸고 부모 노드와 비교해서 자리 바꿈
        //주의할 점 오른쪽 자식노드가 전체 트리 크기보다 작거나 같아야한다. 크면 말이 안되니까
}