[BOJ] 11286: 절댓값 힙(JAVA)

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

11286번: 절댓값 힙

문제

절댓값 힙은 다음과 같은 연산을 지원하는 자료구조이다.

1. 배열에 정수 x (x ≠ 0)를 넣는다.
2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.

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

입력

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

출력

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

예제 입력 1 복사

18

1

-1

0

0

0

1

1

-1

-1

2

-2

0

0

0

0

0

0

0

 

예제 출력 1 복사

-1

1

0

-1

-1

1

1

-2

2

0

 

---

[문제 풀이]

최소힙의 원소 삽입, 제거와 같은 방식으로 절댓값 힙을 구성하면되는데, 원소 정렬의 기준이 절댓값인 것이다. 따라서 원소의 크기 자체를 비교하는 것이 아닌, Math.abs()를 이용해 절댓값을 비교하고 더 작은 값을 상위 노드에 저장하면 된다. 

만약 두 절댓값이 같다면, 원래 수들 중 더 작은 값을 상위 노드에 저장한다.

 

원소 삽입 과정은 다음과 같다.

heap의 끝에 해당 수를 넣고, 이 원소의 위치를 조정해주어야 한다.

부모 노드의 인덱스인 idx/2가 1보다 작거나 같아지거나 (더이상 비교할 노드가 존재하지 않는 경우), 해당 수의 절댓값이 부모 노드의 절댓값보다 크거나, 해당 수의 절댓값이 부모 노드의 절댓값과 같고 해당 수가 부모노드 수보다 크거나 같을 때까지 반복문을 진행한다.

위의 조건에 걸리지 않는다면 해당 노드와 부모 노드의 수를 교환한다. 

 

원소 삭제 과정은 다음과 같다.

힙의 루트 원소, 즉 1번째 원소는 최대 힙에서 절댓값이 가장 작은 원소들 중 수가 가장 작은 수이다. 따라서 해당 원소를 min 정수 변수에 저장해두고, heap의 마지막 노드와 루트를 교환한다. 그 후 마지막 노드를 삭제하면 기존 루트 노드의 값은 삭제되고, 마지막 인덱스의 노드의 값은 루트에 존재하게 된다. 따라서 다시 이를 절댓값 힙으로 유지하기 위해서는 루트 노드의 위치를 조정해주어야 한다. 만약 교환한 노드의 값이 절댓값이 가장 작은 원소들 중 수가 가장 작은 수라면 절댓값 힙이 유지되므로 단지 값을 삭제하기만 하면 된다.

그렇지 않다면 자식 노드와 비교해 절댓값이 더 작으며 수가 더 작은 값을 부모 노드로 조정해주어야 한다.

자식 노드의 인덱스는 현재 노드의 인덱스 * 2 (왼쪽 자식 노드), 현재 노드의 인덱스 * 2 + 1 (오른쪽 자식 노드) 두 가지가 존재할 수 있다. 만약 자식 노드가 왼쪽, 오른쪽 모두 존재한다면, 둘 중 절댓값이 더 작거나, 만약 두 수의 절댓값이 같다면 수의 크기가 더 작은 값을 가진 노드와 해당 노드의 값을 비교하며 절댓값 힙을 유지한다.

 

1. 입력받은 수가 0이고,

    1-1. heap이 비어있지 않다면 힙에서 원소를 삭제하고 해당 원소를 stringbuilder에 append 시킨다.

    1-2. heap이 비어있다면 stringbuilder에 0을 append 시킨다.

2. 입력받은 수가 0이 아니라면 힙에 입력 받은 수를 넣어준다.

 

[코드]

import java.util.*;

public class Main {

    static StringBuilder sb= new StringBuilder();
    static ArrayList<Integer> heap;
 
     public static void insert(int n) {
        heap.add(n);
        int idx = heap.size()-1;

         while(idx>1 && (Math.abs(n)<Math.abs(heap.get(idx/2))||(Math.abs(n)==Math.abs(heap.get(idx/2)) && n<=heap.get(idx/2)) )){
               int temp = heap.get(idx);
               heap.set(idx, heap.get(idx/2));
               heap.set(idx/2, temp);
               idx = idx/2;

           }
    }


      public static void pop() {
          if(heap.size()-1<1){
              sb.append(0+"\n");
              return;
          }

         else{
             int min = heap.get(1);
             heap.set(1, heap.get(heap.size()-1));
             heap.set(heap.size()-1, min);
             heap.remove(heap.size()-1);

              int idx = 1;

              while(idx*2<heap.size()) {
                  int ch = heap.get(idx*2);
                  int ch_idx = idx*2;

                  if(idx*2+1<heap.size() && (Math.abs(ch)>Math.abs(heap.get(idx*2+1))|| (Math.abs(ch)==Math.abs(heap.get(idx*2+1)) && ch>heap.get(idx*2+1)) )) {
                       ch = heap.get(idx*2+1);
                       ch_idx = idx*2+1;

                   }

                   if(Math.abs(heap.get(idx))<Math.abs(ch)||(Math.abs(heap.get(idx))==Math.abs(ch)&&heap.get(idx)<=ch))
                       break;

                   int temp = heap.get(idx);
                   heap.set(idx, ch);
                    heap.set(ch_idx, temp);
                    idx = ch_idx;
             }
             sb.append(min+"\n");
         }


    }
    public static void main(String[] args) {
    
      Scanner sc = new Scanner(System.in);

      
      heap = new ArrayList<>();
      int N = sc.nextInt();
      int x;
      heap.add(0); //0번째 원소 사용 x
      
      while(N>0) {
       x = sc.nextInt();
       
       if(x==0)
           pop();
       
       else 
           insert(x);
       
       N--;
       
      
      }
      
      
      System.out.println(sb.toString());
   }
}