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

문제

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

문제 풀이

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static StringBuilder result = new StringBuilder();
    static int cnt = 0;
    static int k;
    static boolean flag = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] A = new int[N + 1]; //입력받은배열요소 수 + 더미데이터 1
        for (int i = 1; i < A.length; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        heapSort(A);
    }

    private static void heapSort(int[] arr) {
        buildHeap(arr, arr.length - 1);
        for (int i = arr.length - 1; i > 1; i--) {
            swap(arr, 1, i);
            heapIfy(arr, 1, i - 1);
        }
        if (flag) {
            System.out.println(result);
        } else {
            System.out.println("-1");
        }
    }

    private static void buildHeap(int[] arr, int n) {
        for (int i = n / 2; i >= 1; i--) {
            heapIfy(arr, i, n);
        }
    }

    private static void heapIfy(int[] arr, int i, int n) {
        int left = 2 * i;
        int right = left + 1;
        int smaller = 0;
        if (right <= n) {
            smaller = arr[left] < arr[right] ? left : right;
        } else if (left <= n) {
            smaller = left;
        } else {
            return;
        }
        if (arr[smaller] < arr[i]) {
            swap(arr, i, smaller);
            heapIfy(arr, smaller, n);
        }
    }

    private static void swap(int[] arr, int a, int b) {
        cnt++;
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
        if (cnt == k) {
            flag = true;
            for (int i = 1; i < arr.length; i++) {
                result.append(arr[i]);
                if(i < arr.length-1){
                    result.append(" ");
                }
            }
        }
    }
}