[Baekjoon/Java] 알고리즘 수업 - 힙 정렬 2

문제

24174번: 알고리즘 수업 - 힙 정렬 2

풀이

문제에서 제시하는 다음 수도 코드를 그대로 구현하면 되는 문제이다. 단, K번 교환될때의 배열을 저장하는 부분만 추가해주어야한다.

import java.util.*;
import java.util.stream.Collectors;

public class Main {
    private static String answer = "-1";
    private static int TARGET = 0;
    private static int cnt = 1;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int K = scanner.nextInt();
        TARGET = K;
        int[] arr = new int[N+1];
        for (int i=1; i<N+1; i++) {
            arr[i] = scanner.nextInt();
        }
        heap_sort(arr, N);
        System.out.println(answer);
    }

    private static String arrayToString(int[] array) {
        List<String> collect = Arrays.stream(array).mapToObj(String::valueOf).collect(Collectors.toList());
        return String.join(" ", collect).substring(2);
    }

    private static void caching(int[] A) {
        if (cnt  TARGET) {
            answer = arrayToString(A);
        }
        cnt++;
    }

    private static void heap_sort(int[] A, int n) {
        build_min_heap(A, n);
        for (int i=n; i>=2; i--) {
            int temp = A[1];
            A[1] = A[i];
            A[i] = temp;
            caching(A);
            heapify(A, 1, i - 1);
        }
    }

    private static void build_min_heap(int[] A, int n) {
        for (int i=n/2; i>=1; i--) {
            heapify(A, i, n);
        }
    }

    private static void heapify(int[] A, int k, int n) {
        int left = 2 * k, right = 2 * k + 1;
        int smaller;
        if (right <= n) {
            if (A[left] < A[right]) {
                smaller = left;
            } else {
                smaller = right;
            }
        } else if (left <= n) {
            smaller = left;
        } else {
            return;
        }

        if (A[smaller] < A[k]) {
            int temp = A[k];
            A[k] = A[smaller];
            A[smaller] = temp;
            caching(A);
            heapify(A, smaller, n);
        }
    }
}

시간 복잡도: O(n logn)