11286번

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

11286번: 절댓값 힙

이 문제는 저번에 풀었던 힙 최대 최소 문제와 같은 로직이다.

다만 추가적으로 절댓값을 비교하고 절댓값이 같다면 원래의 값을 비교하여 처리하는 방식이다.

저번에 구현했던 힙 자료구조를 그대로 이용하여서 이 문제를 해결하였다.

먼저 입력값을 저장할 int형 배열과 배열의 크기를 판단할 size변수를 설정하고, 그다음에 힙의 불완전 트리구조를 구현할 메서드를 정의한다.

메서드는 왼쪽, 오른쪽 자식노드 접근 메서드와 노드 추가, 삭제 메서드로 구현된다.

메서드를 구현한 후에 입력값이 0인 경우에는 삭제 메서드를 호출하고 그렇지 않으면 추가 메서드를 호출하여 값을 얻어낸다.

 

이때 노드의 추가와 삭제 과정에서 힙의 트리를 재배치 해야하는데 이때 절댓값을 이용해서 재배치를 한다.

노드 추가시 추가하려는 값의 절댓값이 부모노드의 값보다 작다면 자리를 바꿔준다. 만약 절댓값은 같으나 크기가 다르다면, 원래의 값을 비교하여 추가하려는 값이 부모노드의 값보다 작으면 자리를 바꿔준다.

마찬가지로 노드 삭제시에는 마지막노드를 제일 위로 가져와서 아래의 왼쪽, 오른쪽 자식노드와 절댓값을 비교해서 크다면, 자리를 바꿔준다. 여기서 왼쪽과 오른쪽 자식노드 중에 어느 것과 바꿀지도 값을 비교한다.

 

 

 

힙 구현에 대한 추가적인 설명은 아래의 글을 통해서 확인하면 좋겠다.

https://parkjunbackend.tistory.com/43

b11279번

 

정답코드는 아래와 같다.

package backjoon.b11286;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

public class b11286 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        heap h = new heap(N);
        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            int tmp = Integer.parseInt(br.readLine());
            if(tmp==0){
                sb.append(h.poll()).append("\n");
            }
            else h.offer(tmp);
        }
        System.out.println(sb);
    }
}
class heap{
    int[] arr;
    int size;
    public heap(int n){
        this.arr=new int[n+1];
        this.size=0;
    }
    public int rightSon(int n){
        return n*2+1;
    }
    public int leftSon(int n){
        return n*2;
    }
    public int getParent(int n){
        return n/2;
    }
    public boolean isEmpty(){
        return size==0;
    }
    public void offer(int value){
        shiftUp(size+1,value);
        size++;
    }
    public void shiftUp(int idx,int target){
        while (idx>1){
            int parent = getParent(idx);
            int parentVal = arr[parent];


            if(Math.abs(target)>Math.abs(parentVal)){
                break;
            }
            if(Math.abs(target)==Math.abs(parentVal)){
                if(target>=parentVal){
                    break;
                }
            }
            //p=-2 c=1
            arr[idx]=parentVal;
            idx=parent;

        }
        arr[idx]=target;
    }

    public int poll(){
        if(isEmpty()){
            return 0;
        }
        int result = arr[1];
        int target = arr[size];
        arr[size]=0;
        size--;
        shiftDown(1,target);
        return result;
    }
    public void shiftDown(int idx, int target){
        arr[idx]=0;
        int parent = idx;
        int child;
        while ((child=leftSon(parent))<=size){

            int right = rightSon(parent);
            int childVal = arr[child];
            if(Math.abs(arr[right])<Math.abs(childVal) && right<=size){
                child=right;
                childVal=arr[right];
            }
            if(Math.abs(arr[right])==Math.abs(childVal) && right<=size){
                if(arr[right]<childVal){
                    child=right;
                    childVal=arr[right];
                }
            }
            if(Math.abs(target)<Math.abs(childVal)){
                break;
            }
            if(Math.abs(target)==Math.abs(childVal)){
                if(target<=childVal){
                    break;
                }
            }
            arr[parent]=childVal;
            parent=child;
        }
        arr[parent]=target;
    }
}