[BOJ] 11279: 최대 힙(JAVA)

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

11279번: 최대 힙

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

1. 배열에 자연수 x를 넣는다.
2. 배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

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

입력

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

출력

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

예제 입력 1 

13

0

1

2

0

0

3

2

1

0

0

0

0

0

예제 출력 1

0

2

1

3

2

1

0

0

 

---

[문제 풀이]

해당 문제는 최대 힙, 또는 우선순위큐를 이용하여 풀 수 있다. 출력할 때 stringbuilder 이용하지 않고 System.out.println() 사용하면 시간초과난다..

 

최대 힙을 이용하는 방법은 다음과 같다.

힙을 arraylist로 선언하고, 0번째 index는 사용하지 않을 예정이므로 0을 append 한다.

 

힙에 원소를 넣는 과정은 다음과 같다. arraylist의 마지막에 해당 원소를 넣고, 부모 노드의 값보다 해당 원소의 크기가 더 크다면 자리를 바꿔줘야 한다. 부모 노드의 인덱스는 마지막 원소의 인덱스 즉, heap.size()-1 의 절반인 (heap.size()-1)/2 이다. 따라서 heap.get(heap.size()-1) 과 heap.get((heap.size()-1)/2) 를 비교하여 만약 삽입한 원소가 더 크다면 자리를 바꿔준다. 이를 해당 원소가 부모노드보다 크지 않을 때까지, 또는 해당 원소가 루트에 도달할 때까지 반복하여 최대 힙을 유지한다.

 

힙에서 원소를 삭제하는 방법은 다음과 같다.

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

그렇지 않다면 자식 노드와 비교해 더 큰 값을 부모 노드로, 작은 값은 자식 노드로 조정해주어야 한다.

자식 노드의 인덱스는 현재 노드의 인덱스 * 2 (왼쪽 자식 노드), 현재 노드의 인덱스 * 2 + 1 (오른쪽 자식 노드) 두 가지가 존재할 수 있다. 만약 자식 노드가 왼쪽, 오른쪽 모두 존재한다면, 둘 중 더 큰 값을 가진 노드와 해당 노드의 값을 비교한다. 자식 노드가 현재 노드 보다 크다면, 자식 노드를 현재 노드 위치로 올리고, 현재 노드의 값을 자식 노드에 저장한다. 이를 현재 노드가 자식 노드보다 커질 때까지, 또는 리프 노드에 도달할 때 까지 진행한다.

 

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

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

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

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

 

 

우선순위 큐를 이용하는 방법은 다음과 같다.

큐는 FIFO의 특성을 가져 가장 앞의 원소가 먼저 POP되는 특성을 가지고 있다. 따라서 맨 앞의 원소가 가장 큰 값을 가져야 최대 힙의 특성을 갖는 우선순위 큐를 생성할 수 있다. 우선순위 큐는 오름차순 정렬되는 것이 기본값이기 때문에 Collections.reverseOrder()을 이용하여 내림차순 정렬되는 우선순위 큐를 만들어야 한다.

우선순위 큐는 별다른 함수 구현 없이 자동으로 순서를 조정해주므로 

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

    1-1. 우선순위 큐가 비어있지 않다면 큐에서 원소를 삭제하고, stringbuilder에 append 시킨다.

    1-2. 우선순위 큐가 비어있다면 stringbuilder에 0을 append 시킨다.

2. 입력받은 수가 0이 아니라면 우선순위 큐에 입력 받은 수를 넣어준다.

 

---

 

 

[코드 - 최대 힙]

import java.util.*;

public class Main {

    static ArrayList<Integer> heap;
    static StringBuilder sb= new StringBuilder();
    public static void insert(int n) {
        heap.add(n);
        int idx = heap.size()-1;
        while(idx>1&&heap.get(idx)>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 print() {
        if(heap.size()-1<1) {
            sb.append(0+"\n");
            return;
        }
        else {
            int max = heap.get(1);

            heap.set(1, heap.get(heap.size()-1));
            heap.set(heap.size()-1, max);
            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()&&ch<heap.get(idx*2+1)) {
                    ch = heap.get(idx*2+1);
                    ch_idx = idx*2+1;
                }

               if(heap.get(idx)>ch) 
                   break;


              int temp = heap.get(idx);
              heap.set(idx, ch);
              heap.set(ch_idx, temp);
              idx = ch_idx;
         }

         sb.append(max+"\n");

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

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

---

[코드 - 우선순위 큐]

import java.util.*;

public class Main {

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

      StringBuilder sb= new StringBuilder();
      int N = sc.nextInt();
      PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
      int x;
      while(N>0) {
        x = sc.nextInt();
       
        if(x==0) {
            if(pq.size()>0)
                 sb.append(pq.poll()+"\n");
            else
                 sb.append(0+"\n");
         }
        else {
            pq.add(x);
        }
        N--;
      }
      
    
      System.out.println(sb.toString());
   }
}