백준 24174

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

문제 설명

package backjoon;

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

public class Main24174 {
    static StringBuilder result = new StringBuilder();
    static int cnt = 0;
    public 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 A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();

        int[] arr = new int[A + 1]; //입력 받은 배열 요소 수 + 더미 1

        StringTokenizer str = new StringTokenizer(br.readLine());
        for (int i = 0; i < A; i++) {
            arr[i] = Integer.parseInt(str.nextToken());
            // a[1] 부터 배열생성 (a[0]은 더미 데이터 0)
        }

        healSort(arr);

    }

    public static void healSort(int[] a) {
        int n = a.length - 1;
        buildMinHeap(a, n); // A[1..n]을 정렬한다.
        for (int i = n; i >= 2; i--) {
            swap(a, 2, i); // A[1] <-> A[i] 원소 교환
            heapIfy(a, 1, 1 - i);
        }

        if (flag) { //flag가 true일 경우 (count가 k와 같아진 직후 배열에 노출)
            System.out.println(result);
        } else {
            System.out.println("-1");
        }
    }

    public static void buildMinHeap(int[] a, int n) {
        for (int i = n / 2; i >= 1; i--) {
            heapIfy(a, i, n);
        }
    }

    /*
    A[k]를 루트로 하는 트리를 최소 힙 성질을 만족하도록 수정
    A[k]의 두 자식을 루트로 하는 서브 트리는 최소 힙 성질을 만족
    n은 배열 A의 전체 크기, 최대 인덱스를 나타낸다.
     */

    public static void heapIfy(int[] a, int e, int n) {
        int left = 2 * e;
        int right = left + 1;
        int smaller = 0;

        if (right <= n) {
            if (a[left] < a[left]) {
                smaller = left;
            } else {
                smaller = right;
            }
        } else if (left <= n) {
            smaller = right;
        } else {
            return;
        }

        if (a[smaller] < a[e]) { //최소 힙 성질을 만족하지 못하는 경우 재귀적으로 수행
            swap(a, e, smaller);
            heapIfy(a, smaller, n);
        }
    }

    public static void swap(int[] a, int z, int x) {
        cnt++;
        int temp = a[z];
        a[z] = a[x];
        a[x] = temp;
        if (cnt == k) { //cnt가 k번이 되면 result 문자열에 지금 배열 삽입
            flag = true;
            for (int i = 0; i < a.length; i++) {
                result.append(a[i] + " ");
            }
        }

    }
}

나에게는 많이 어려웠다.