[백준] 11286 : 절댓값 힙

문제 출처: https://www.acmicpc.net/problem/11286

---

문제

---

시도

 

일단 나름대로 Heap을 작성해봤는데 절댓값 비교 부분으로 인해 실패한다.

 

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

public class Main {

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

        System.out.println("-Answer-");
        StringBuilder sb = new StringBuilder();
        while(n-- > 0) {
            int k = Integer.parseInt(br.readLine());
            if (k == 0) sb.append(ah.isEmpty() ? "0" : ah.poll()).append("\n");
            else ah.insert(k);
        }

        System.out.print(sb);
    }

    static class AbsoluteHeap {
        int[] heap;
        int size;

        public AbsoluteHeap(int n) {
            heap = new int[n + 1];
            size = 0;
        }

        public void insert(int x) {
            heap[++size] = x;
            int cur = size;

            absHeapify(cur);
        }

        public int poll() {
            swap(1, size);
            int cur = size - 1;

            absHeapify(cur);

            return heap[size--];
        }

        public boolean isEmpty() {
            return size == 0;
        }

        public void swap(int i, int j) {
            int temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
        }

        public void absHeapify(int cur) {
            while(cur > 1) {
                int parent = cur / 2;
                int absPar = Math.abs(heap[parent]);
                int absCur = Math.abs(heap[cur]);

                if (absPar < absCur || (absPar == absCur && heap[parent] > heap[cur])) {
                    swap(parent, cur);
                    cur = parent;
                } else {
                    break;
                }
            }
        }
    }
}

 

 

---

풀이

 

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

public class Main {

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

        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
            int absA = Math.abs(a);
            int absB = Math.abs(b);

            if (absA > absB) {
                return absA - absB;
            } else if (absA == absB) {
                if (a > b) return a - b;
                else return -1;
            } else
                return -1;
        });


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

        StringBuilder sb = new StringBuilder();
        while (n-- > 0) {
            int k = Integer.parseInt(br.readLine());
            if (k == 0) {
                sb.append(pq.isEmpty() ? "0" : pq.poll()).append("\n");
            } else {
                pq.offer(k);
            }
        }

        System.out.print(sb);
    }

}

 

 

 

풀이 출처 : https://dy-coding.tistory.com/entry/%EB%B0%B1%EC%A4%80-11286%EB%B2%88-%EC%A0%88%EB%8C%93%EA%B0%92-%ED%9E%99-java

---

알게 된 점

 - 절댓값으로 인해 PriorityQueue가 아닌 힙으로 직접 구현해야 하는 줄 알았는데 Comparator 인터페이스로 구현이 가능하다는 점이 신기하고 새롭게 배워야 할 것을 정리했다.

• Comparator와 Comparable (링크)
• Object 클래스의 equals()와 hashCode() (링크)