2022.06.29 백준 Q1927

학습 내용 : 최소 힙 구현, PriorityQueue API를 이용한 최소힙 구현

이 문제는 최소 힙을 구현하는 문제이다. 필자는 API 사용 없이 구현을 한 후에 API를 사용해 구현하였다.

static void addData(int data){
    int currentIndex = ++size;
    while (currentIndex != 1 && list[currentIndex / 2] > data) {
        list[currentIndex] = list[currentIndex / 2];
        currentIndex = currentIndex / 2;
    }
    list[currentIndex] = data;
}

위 코드는 addData를 구현한 코드이다.

currentIndex = ++size를 해 size를 하나 늘려주고 list 끝에 데이터를 넣는다(바로 다음에 swap될 수 있으므로 실제로 넣진 않는다. currentIndex가 1이 아니고(root Index는 더이상 위로 올라갈 수 없기 때문에) list[current/2[(부모 노드)가 data보다 크면 최소 힙을 만족시키기 위해 부모 노드와 자식 노드를 바꾼다(바로 또 바뀔 수 있기 때문에 복잡도를 줄이기 위해 부모 노드만 자식 노드에 넣어놨다). 그 후 부모노드의 부모노드와 비교하기 위해

currentIndex = currentIndex / 2;

를 한다.

 

만약 부모노드가 data보다 작으면 최소힙이 만족하기 때문에 반복문을 빠져나가고 현재 index에 data를 넣어 함수를 종료한다.

 

static void deleteData(){
    if(size==0){
        sb.append(0).append("\n");
        return;
    }
    sb.append(list[1]).append("\n");
    int data = list[size--];
    int currentIndex = 1;
    int child = 2;
    while(child<=size){
        if(child<size&&list[child]>list[child+1]) child++;
        if(data<=list[child]) break;
        list[currentIndex] = list[child];
        currentIndex =child;
        child*=2;
    }
    list[currentIndex] =data;

}

다음은 노드 삭제 함수이다. 첫번째 Index값이 제일 작은 값이므로 그 값을 삭제한다(동시에 출력해준다). 제일 마지막에 있는 노드를 루트 노드에 올리고 size--한다.

반복문에서 child>size면 자식 노드가 없는 것이기 때문에 반복문을 종료한다. child<size(오른쪽 자식이 존재하는지 확인)

일때 왼쪽 자식노드가 오른쪽 자식 노드보다 크면 child++로 오른쪽 자식과 부모 노드를 비교하게 셋팅한다.

만약 data가 더 작다면 최소힙이 만족하기 때문에 반복문을 종료하고 그 것이 아니라면 자식 노드를 부모 노드에 넣고 

currentIndex =child;
child*=2;

후 다시 반복문을 실행한다.

반복문이 끝났다면 현재 노드에 data를 넣어준다.

 

 

-구현 코드-

package BaekJoon1927;

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

public class Main {
    static int[] list;
    static int size =0;
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        list = new int[num];

        for(int i=0;i<num;i++){
            int data = Integer.parseInt(br.readLine());
            if(data==0) deleteData();
            else addData(data);
        }
        System.out.println(sb);
    }


    static void deleteData(){
        if(size==0){
            sb.append(0).append("\n");
            return;
        }
        sb.append(list[1]).append("\n");
        int data = list[size--];
        int currentIndex = 1;
        int child = 2;
        while(child<=size){
            if(child<size&&list[child]>list[child+1]) child++;
            if(data<=list[child]) break;
            list[currentIndex] = list[child];
            currentIndex =child;
            child*=2;
        }
        list[currentIndex] =data;

    }
    static void addData(int data){
        int currentIndex = ++size;
        while (currentIndex != 1 && list[currentIndex / 2] > data) {
            list[currentIndex] = list[currentIndex / 2];
            currentIndex = currentIndex / 2;
        }
        list[currentIndex] = data;
    }
}

 

 

 

아래 코드는 API를 사용해 구현한 코드이다

package BaekJoon1927;

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

public class MakeWithPriorityQueue {
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num = Integer.parseInt(br.readLine());
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        for(int i=0;i<num;i++){
            int data = Integer.parseInt(br.readLine());
            if(data==0) {
                if(queue.isEmpty()) sb.append(0).append("\n");
                else {
                    sb.append(queue.poll()).append("\n");
                }
            }
            else{
                queue.add(data);
            }
        }
        System.out.println(sb);
    }
}

 

우선순위큐는 기본적으로 작은 것 부터 빠져나가기 때문에 최소힙과 같은 동작원리이다. 따라서 넣을 때는 queue.add(data)로 넣고 삭제할때는 queue.poll()로 큐에서 빼면 된다.

만약 다른 방식대로 우선순위를 정하고 싶을때는 comparator나 comparable로 그 조건을 바뀌어준다.