백준 1927 번: 최소힙 (java) - 직접 힙 구현

문제

1927번: 최소 힙

난이도 : 실버 2

유형 : 자료 구조, 우선순위 큐

 

접근법

백준의 문제 유형에 우선순위 큐 라고 되어 있지만 이 문제를 java util class PriorityQueue 갖다 쓰는것은 풀이에 의미가 없다고 생각한다. 물론 우선순위큐는 최소힙으로 구현 되는구나 라는것을 알수도있다 하지만 내 생각에는 해당문제는 최소힙의 알고리즘을 직접 구현하며 이해하기 위함이라고 생각한다.

풀이를 끝내면 구글에 검색하여 다른 사람들은 어떤풀이를 했는지 비교해보는데 상위 게시글 모두 우선순위큐로 구현되어 있어 꼭 작성해야겠다는 생각도 들었다.

---

(1) 우선순위큐

PrioriryQueue 가 최소힙으로 구현되어 있다는것을 알기만 하면 다른 설명없이 풀이가 가능하다

 

(2) 최소힙

-insert 

1. MinHeap class 인스턴스 맴버중 CurrentSize 는 값이 삾입 될때마다 +1

2. 새로운 값 입력시 Currentsize부터(root node) ~ CurrentSize/2 를 반복하여 삽입될 위치 탐색

3. 반복 할때마다 Swap() 함수로 삽입될 노드와 상위 노드 비교하며 자리 변경

-delete

1. 배열 사이즈가 0 이면 비엇으므로 0 리턴

2. root 변수에 기존 root 노드의 값 저장

3. root노드에 마지막 노드의 삽입

4-1. index 1(root) 부터 마지막 노드까지 비교탐색

4-2. 반복 탐색시 조건은 

1. 하위 노드 왼쪽 오른쪽 노드 둘다 마지막 노드보다 크다면 정지
2. 1의 경우가 아니라면 하위노드중 가장 작은값으로 이동

5. 삭제된 기존 root 값 리턴

 

풀이

(1) 우선순위큐 활용

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

public class BOJ1927 {
    static int N;
    static PriorityQueue<Integer> pq = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        JavaLib(bf);
        
    }
    public static void JavaLib(BufferedReader bf) throws IOException{
        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(bf.readLine());
            if (x == 0) { //최소힙 delete
                if(pq.isEmpty()){
                    System.out.println(0);
                }else{
                    System.out.println(pq.poll());
                }
            } else {
                pq.offer(x);
            }
        }
    }
}

 

(2) 최소 힙 구현

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

public class BOJ1927 {
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());
        MinHeap mh = new MinHeap(100001);
        for (int i = 0; i < N; i++) {
            int x = Integer.parseInt(bf.readLine());
            if (x == 0) { //최소힙 delete
                System.out.println(mh.delete());
            } else {
                mh.insert(x);
            }
        }
    }
    public static class MinHeap{
        int[] HeapArray;
        int CurrentSize;
         public MinHeap(int size){
             HeapArray = new int[size];
        }
        private void insert(int x){
            HeapArray[++CurrentSize] = x;
            for(int i =CurrentSize; i>1; i/=2){
                if(HeapArray[i]  > HeapArray[i/2]){
                    break;
                }
                Swap(i/2, i);
            }
        }
        private int delete(){
            if(CurrentSize==0){
                return 0;
            }
            int root = HeapArray[1];
            HeapArray[1] =  HeapArray[CurrentSize];
            CurrentSize--;

            for(int i=1;  i*2<=CurrentSize;){
                if(HeapArray[i] < HeapArray[i*2] && HeapArray[i] < HeapArray[i*2+1] ){
                    break;
                }

                if(HeapArray[i*2] < HeapArray[i*2+1] ){
                    Swap(i*2, i);
                    i= i*2;
                }else{
                    Swap((i*2+1), i);
                    i= i*2+1;
                }
            }

            return root;
        }
        private void Swap(int A, int B){
            int temp = HeapArray[A];
            HeapArray[A] = HeapArray[B];
            HeapArray[B] = temp;
        }
    }

}