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

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

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

풀이 접근법 : 위 문제는 heapify( heap 구조로 증명) 하면서 최소값을 root로 옮긴 후 가장 뒤로 보내면서 정렬하는 슈도 코드를 가지고 있다. 값이 변경될 때에 cnt를 하나씩 올리면서 입력된 targetcnt와 같으면 그 때 arr 값을 출력하는 것으로 접근하였다.

 

 초기 코드를 백준에 제출하였을 때 시간 초과로 문제가 풀리지 않았고, 답을 찾는 과정에서 다른 사람들의 풀이를 찾아보게 되었다...... 풀이의 핵심은 정렬이 완료될 때 까지 기다리지 않고, cnt == targetcnt 일 때 출력한 후 강제 종료하거나 exception 만들어 던져주는 분도 있었다..

 

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

public class Main {

    public static int cnt = 0, target = 0;
    public static int[] output;
    public static boolean isOut = false;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int num = Integer.parseInt(st.nextToken());
        target = Integer.parseInt(st.nextToken());
        int[] arr = new int[num + 1];
        arr[0] = 0;
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i < arr.length; i++) arr[i] = Integer.parseInt(st.nextToken());
        heapSort(arr);
        if (!isOut) {
            System.out.print(-1);
        }
    }

    public static void swap (int[] arr, int a, int b){
        cnt++;
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
        if(cnt == target){
            StringBuilder sb = new StringBuilder();
            for (int i = 1; i < arr.length; i++) {
                sb.append(arr[i]);
                sb.append(" ");
            }
            System.out.print(sb.toString());
            isOut = true;
        }
    }

    public static void heapSort(int[] arr) {
        buildMinHeap(arr, arr.length - 1);
        for (int i = arr.length - 1; i > 1 ; i--) {
            swap(arr, 1 , i);
            heapify(arr, 1, i - 1);
        }
    }

    public static void buildMinHeap(int[] arr, int num) {
        for (int i = num / 2; i >= 1 && !isOut; i--) {
            heapify(arr, i, num);
        }
    }

    public static void heapify(int[] arr, int k, int num) {
        int left = 2 * k;
        int right = 2 * k + 1;
        int smaller = -1;

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

        if (arr[smaller] < arr[k]) {
            swap(arr,k,smaller);
            heapify(arr, smaller, num);
        }
    }
}