[백준] 11279 - 최대 힙

백준 바로가기

11279번: 최대 힙

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

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

오랜만에 알고리즘 문제를 업로드 합니다. 정처기 시험이 끝나고 처음이네요. 우선순위 큐라는 알고리즘인데, 문제에선 힙(Heap) 자료구조를 구현하도록 되어있습니다. 힙을 간략하게 알아보자면

• 완전 이진트리의 일종
  • 반정렬 상태(완전히 정렬된 상태가 아님)이며, 완전 이진트리와는 다르게 중복값이 허용
    힙의 삽입과 삭제의 시간 복잡도는 최악의 경우 최하단 노드로부터 최상단 노드까지 스왑이 필요하게 됩니다. 
    따라서 O(log N)의 시간 복잡도를 가집니다.
    보통 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적이기 때문
  • 힙은 최대힙과 최소힙으로 나누어지고, 최대힙은 부모 노드가 가장 큰 것이며 최소힙은 부모 노드가
    가장 작음
  • 힙의 규칙에 따라 트리의 가장 상단에는 최댓값 또는 최솟값이 있는 것이 자명하기 때문에,
    O(1) 만에 최댓값과 최솟값을 찾을 수 있음
  • 힙 자료구조는 보통 배열을 이용하며, 0번째 인덱스는 편하게 구현하기 위해서 사용하지 않음
  • 1번째 인덱스부터 시작하면, 해당 인덱스의 자식 노드는 각각 *2, *2+1로 나타낼 수 있음
    (1번째 인덱스의 자식노드는 좌:1*2, 우:1*2+1이다)
  • 마찬가지로 자식노드 위치(N)에서 부모노드 인덱스는 N/2로 표현할 수 있음

https://www.geeksforgeeks.org/heap-data-structure/

이렇게 트리형태로 이루어져있고 노드들로 구성되어 있습니다. 

문제로 돌아가서 풀이법은 두 가지가 있습니다. 하나는 Java API를 활용하는 것이고 나머지 하나는 실제 heap을 List나 Array를 이용해 직접 구현하는 방법입니다. 전자는 PriorityQueue<E>를 선언해서 메서드로 insert와 delete를 수행할 수 있기에 설명을 스킵하겠습니다. 후자는 복잡한 대신 heap 구조를 이해할 수 있는 방법입니다. 안타깝게도 제가 쓴 코드는 로직은 맞는데 예외 케이스가 있는지 '틀렸습니다'를 때려 맞고 있어서 로직만 참고하시고 코드는 따지 않으시면 됩니다.

1. insert

자식노드는 부모노드 index의 1/2입니다. 실제 트리를 그려보시면 바로 알 수 있습니다. 자식은 둘인데 int로 1/2하면 소수점 버리고 부모노드 index로 같은 값이 나옵니다. 저는 List를 썼기 때문에 add 하면 List의 마지막 인자로 추가됩니다. size가 1이면 반복문이 실행되지 않도록 조건을 넣어줬습니다. 부모노드와 크기 비교를 해가면서 자식이 더 클 경우 위치를 set을 사용해 교체해줍니다. 

2. delete

insert보다 복잡한데요, 맨 처음 노드를 삭제해준 후 나머지 노드들을 최소힙에 맞게 정렬해주면 됩니다. 자식노드의 좌, 우 노드를 모두 고려해야 되므로 크기를 비교해주는 과정이 추가되었습니다.

 

package baekJoon.week18;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
 
public class MaxHeap_11279_ex3 {
 
    static List<Integer> heap = new ArrayList<>();
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        heap.add(0, null);
 
        int reps = Integer.parseInt(br.readLine());
        while (reps-- > 0) {
            int number = Integer.parseInt(br.readLine());
            if (number == 0) {
                sb.append(delete() + "\n");
            } else {
                insert(number);
            }
        }
        System.out.println(sb.toString());
    }
 
    public static void insert(int number) {
 
        heap.add(number);
 
        for (int i = heap.size() - 1; i > 0; i /= 2) {
            if (heap.get(i) > heap.get(i / 2)) {
                int temp = heap.get(i);
                heap.set(i, heap.get(i / 2));
                heap.set(i / 2, temp);
            } else {
                break;
            }
        }
    }
 
    public static int delete() {
        if (heap.size() == 1) {
            return 0;
        }
 
        int deleteNum = heap.get(1);
        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);
 
        int pos = 1;
        for (int i = pos; i * 2 < heap.size(); ) {
            int currentNum = heap.get(i);
            int child1 = heap.get(i * 2);
 
            int maxChild = i * 2;
            if (heap.size() > i * 2 + 1) {
                int child2 = heap.get(i * 2 + 1);
                if (child1 < child2) {
                    maxChild = i * 2 + 1;
                    int temp2 = child1;
                    child1 = child2;
                    child2 = temp2;
                }
            }
 
            if (currentNum > heap.get(maxChild)) {
                break;
            } else {
                int temp3 = currentNum;
                heap.set(i, heap.get(maxChild));
                heap.set(maxChild, currentNum);
            }
        }
        return deleteNum;
    }
}