자료구조 5/13 - Heap

최소 힙 의 구조

연관문제

알고리즘 수업 - 백준 24174번

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


public class Hp {
    static int count = 0;
    static int stepCut;
    static void heap_sort(int[] arr) {
        int n = arr.length - 1;
        build_min_heap(arr, n);
        for (int i = n; i > 1; i--) {
            int tmp = arr[1];
            arr[1] = arr[i];
            arr[i] = tmp;
            // 교환!
            count++;
            if (count == stepCut) {
                System.out.println(Arrays.toString(arr));
                return;
            }
            heapify(arr, 1, i - 1);
        }
    }

    static void build_min_heap(int[] arr, int size) {
        for (int i = size / 2; i > 0; i--) {
            heapify(arr, i , size);
        }
    }

    static void heapify(int[] arr, int target, int size) {
        int left = 2 * target;
        int right = 2 * target + 1;
        int smaller = 0;

        if (right <= size) {
            if (arr[left] < arr[right]) {
                smaller = left;
            } else {
                smaller = right;
            }
        } else if (left <= size) {
            smaller = left;
        } else {
            return;
        }

        if (arr[smaller] < arr[target]) {
            int tmp = arr[target];
            arr[target] = arr[smaller];
            arr[smaller] = tmp;
            // 교환!
            count++;
            if (count == stepCut) {
                System.out.println(Arrays.toString(arr));
                return;
            }
            heapify(arr, smaller, size);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = (br.readLine()).split(" "); // array size, exchange opportunity
        String[] numbers = (br.readLine()).split(" ");
        stepCut = Integer.parseInt(input[1]);

        int[] arr = new int[Integer.parseInt(input[0]) + 1];
        Arrays.fill(arr, 0);

        for (int i = 0; i < numbers.length; i++) {
            arr[i + 1] = Integer.parseInt(numbers[i]);
        }
        heap_sort(arr);

        if (count < stepCut) {
            System.out.println(-1);
        }
    }
}

무슨 문제인지 이해를 하지 못하고 있다가, 다른 분들의 글을 보고 나서 문제에 적혀있는 의사코드를 그대로 작성해서 이용하면 된다는 힌트를 얻고 풀 수 있었다.

의사코드를 처음으로 실제 코드로 작성해보았다. 처음엔 반복문 반대로 작성해서 코드 오류가 났는데 덕분에 의사코드를 좀 더 잘 알게 되었다.