백준 11286번 : 절댓값 힙 java

이 문제는 자료구조 힙 안에 자료를 저장하고 제거하는 기능을 구현하는 문제입니다.

힙이란 완전 이진트리로 구성되어 있는 일종의 자료구조로써 자료들을 저장할 수 있게 도와줍니다.

 

완전 이진 트리란 왼쪽의 그림과 같이 트리가 있을 때 가장 위의 트리부터, 위 층이 다 채워지면 왼쪽부터
채우는 이진 트리를 의미합니다.

트리에서는 자료가 있는 칸을 노드라고 부릅니다.

이 그림에서 노드가 채워지는 순서는 알파벳 순입니다.

 

 

왼쪽의 그림과 같이 왼쪽에서부터 차례대로 채우지
않은 이진 트리는 완전 이진트리가 아닙니다.

 

 

 

힙은 보통 최대 힙, 최소 힙으로 나뉩니다.

 

최대 힙은 다음과 같이 가장 큰 수가 가장 위에 위치한
힙을 나타냅니다.

최대 힙에서는 새로운 자료가 들어오면 비교를 통해
자식 노드보다 부모 노드가 항상 큰 값을 유지하게 합니다.

 

 

여기 14라는 새로운 노드가 원래 노드에 들어왔을 때를 예시로 설명해 드리겠습니다.

힙에서는 새로운 노드가 들어오면 완전 이진트리를
만족시키기 위한 자리로 들어갑니다.

 

 

새로 들어온 노드를 부모 노드와 비교하니
부모 노드보다 새로 들어온 노드의 값이 더 큽니다.

이 힙은 최대 힙이기 때문에 두 노드를 바꿔줍니다.

 

 

 

자리를 바꾼 후 다시 부모 노드와 비교를 해주면 또 부모 노드보다 크니 자리를 바꿔줍니다.

이제 14가 들어가 있는 노드의 부모 노드가 없으니
자리를 고정시켜줍니다.

 

 

이것이 최대 힙에서 자료를 삽입하는 과정입니다.

이번에는 최대 힙에서 자료를 제거하는 과정을 보여드리겠습니다.

최대 힙에서 자료를 제거할 때는 루트 노드를 제거한 후 가장 아래에 있는, 또 가장 오른쪽에 있는 노드를 가져온 후에 비교를 진행합니다.

 

 

다음과 같은 노드에서 제거를 진행해보도록
하겠습니다.

 

 

 

 

루트 노드를 제거하고 동시에 가장 오른쪽에 있는 최하위 노드를 루트 노드의 자리로 가져옵니다.

 

 

 

 

루트 노드의 자식 노드 둘을 서로 비교하면 오른쪽 자식 노드의 값이 더 큽니다.

이 노드와 루트 노드의 값을 비교하였을 때 루트
노드의 값이 더 작기 때문에 자리를 바꾸어줍니다.

이제 자식 노드가 없는 단말 노드가 되었기 때문에 비교를 멈춥니다.

 

최소 힙에서는 루트 노드가 그 완전 이진트리에서 가장 작은 값이고 부모 노드가 자식 노드보다 작아야 된다는 규칙을 제외하고서는 최대 힙과 같은 구조로 이루어져 있습니다.

이 힙을 구현하기 위해서 우선순위 큐라는 자료구조를 이용할 수 있는데 오라클에서는 PriorityQueue라는 api를
제공하고 있습니다.

이 우선 순위 큐의 정렬은 기본적으로 오름차순으로 이루어져 있습니다.

이는 최소 힙의 모양과 같습니다.

이다음부터는 코드를 보면서 설명하겠습니다.

---

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

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

        PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                int A = Math.abs(a);
                int B = Math.abs(b);
                if(A>B)
                    return A-B;

                else if(A == B){
                    if(a>b) return 1;
                    else return -1;
                }

                else
                    return -1;
            }
        });

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

        while(N-->0){
            int num = Integer.parseInt(br.readLine());

            if(num != 0){
                pq.offer(num);
            }
            else{
                if(!pq.isEmpty())
                    sb.append(pq.poll()).append("\n");
                else
                    sb.append("0\n");
            }
        }

        System.out.print(sb);
    }
}

이게 제가 짠 코드입니다.

PriorityQueue<Integer> pq = new PriorityQueue<>(new Comparator<Integer>(){
    @Override
    public int compare(Integer a, Integer b){
        int A = Math.abs(a);
        int B = Math.abs(b);
        if(A>B)
            return A-B;

        else if(A == B){
            if(a>b) return 1;
            else return -1;
        }

이 중에서 PriorityQueue를 선언한 부분은 주의 깊게 보셔야 합니다.

PriorityQueue는 위에서 말씀드린 대로 기본적으로 오름차순으로 정렬이 되어있습니다.

그러나 이 문제에서는 '절댓값'을 기준으로 정렬을 하라고 했습니다.

이렇다면 우리는 PriorityQueue의 정렬 기준을 새로 만들어주어야 합니다.

저는 PriorityQueue의 정렬 기준을 설정해 주기 위하여 Comparator라는 api를 이용하였습니다.

Comparator는 interface의 일종으로 java.util 폴더에 있습니다.

Comparator를 이용하기 위해서는 이 인터페이스 안에 있는 compare라는 추상메소드를 구현해주어야 합니다.

물론 Comparable을 이용하여 compareTo를 구현하여 정렬 기준을 설정해주어도 되지만 비교를 하는 대상이 정수 값
하나이니 더 간편하게 쓸 수 있는 Comparator로 정했습니다.

인터페이스인 Comparator을
Comparator<Integer> cp = new Comparator<Integer>();
위와 같이 구현하는 것은 불가능합니다.

하지만 우리는 Comparator 안에서 유일한 추상메소드인 compare을 오버라이딩해주면서 구현할 수 있습니다.

compare함수를 구현할 때 return 값으로 양수를 주면 순서를 바꾸겠다는 것이고 음수이면 바꾸지 않겠다는 것입니다.

이때 return 값으로 무조건 1이나 -1을 주어야 하는 것이 아니고 음수나 양수이면 가능합니다.
그러나 2^30 - (-2^31)와 같은 연산으로 인하여 표현할 수 있는 범위를 넘어서면 오버플로우가 발생하고 이와 반대로 언더플로우가 발생할 수도 있으니 이에 유의하셔야 합니다.

또한 절댓값이 같으면 음수를 먼저 제거한다고 하였으니 앞으로 보내줍니다.

else if(A == B){
    if(a>b) return 1;
    else return -1;
}

이 부분만 이해하시면 나머지는 쉽게 구현할 수 있으실 겁니다.