[백준] 11286 절댓값 힙

문제보기

오늘의 대 삽질 문제!^^

조건중에 절댓값이 같으면 더 작은 수(음수) 가 우선순위로 오도록 하라고 해서… 이거 때문에 흑ㅎ그..

import java.util.*;
import java.io.*;

public class Main{

  public static void insertHeap(int[] heap, int size, int item){
    int i = ++size;
    while(true){
      if( i == 1 ){
        break;
      }
      int ch = Math.abs(item);
      int pr = Math.abs(heap[i/2]);

      if( ch > pr ){
        break;
      }else if( ch == pr ){ // 만약 두 수의 절댓값이 같다면
        if(item >= heap[i/2]) break; // 부모가 음수거나 둘이 같으면 나오자
      }
      heap[i] = heap[i/2]; 
      i = i/2;
    }
    heap[i] = item;
  }

  public static int deleteHeap(int[] heap, int size){
    int n = size;
    if( size == 0 ){
      return 0;
    }
    int item = heap[1];
    heap[1] = heap[size];
    heap[size] = 2147483647; // 이거 진짜 중요함 ㅠㅠ 절댓값이 가장 큰걸 넣어주자고 생각해서 단순히 -2147483648 넣었다가 아래에서 보면 알겠지만 Math.abs 할때마다 오버플로우(...) 젠장...

    for(int i = 1 ; i*2+1 <= size ;){
      int par = Math.abs(heap[i]);
      int ch1 = Math.abs(heap[i*2]);
      int ch2 = Math.abs(heap[i*2+1]);
      int min = ch1 < ch2 ? heap[i*2] : ch1 == ch2 ? Math.min(heap[i*2], heap[i*2+1])  : heap[i*2+1];  

      if( par < ch1 && par < ch2 ){ // 절댓값이 둘보다 작으면 중단
        break;
      }else if( par == Math.abs(min) && heap[i] <= min ){ // 둘 중 더 작은 애랑 절댓값이 같으면서 값 자체도 작거나 같으면 중단
        break;
      }else if(ch1 < ch2){ // 두 자식 중 더 절댓값이 작은 자식과 교환
        int temp = heap[i];
        heap[i] = heap[i*2];
        heap[i*2] = temp;
        i = i*2;
      }else if(ch1 == ch2){ // 만약 자식 둘이 절댓값이 같다면, 실제값이 더 작은쪽과 교환
        if(heap[i*2] < heap[i*2+1]){
          int temp = heap[i];
          heap[i] = heap[i*2];
          heap[i*2] = temp;
          i = i*2; 
        }else{
          int temp = heap[i];
          heap[i] = heap[i*2+1];
          heap[i*2+1] = temp;
          i = i*2+1;
        }
      }else{ 
        int temp = heap[i];
        heap[i] = heap[i*2+1];
        heap[i*2+1] = temp;
        i = i*2+1;
      }
    }
    return item;
  }


  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());

    int[] heap = new int[t+1];
    Arrays.fill(heap, 2147483647);
    heap[0] = 0;
    int size = 0;

    StringBuilder sb = new StringBuilder();
    while( t-- > 0 ){

      int n = Integer.parseInt(br.readLine());

      if( n == 0 ){
        System.out.println(deleteHeap(heap, size));
        if(size > 0) size--;
      }else{
        insertHeap(heap, size++, n);
      }
    }
  }
}