백준 24174번 힙 정렬2 제로베이스 자료구조 마지막 주제 : Heap

자료구조 1 Page 노트 정리 마지막 주제 : Heap

 

 

백준 24174번 알고리즘 수업 - 힙 정렬 2 문제 풀이

백준 24174번 문제

 

기존 문제에 주어진 의사코드를 그대로 구현 후 원소 교환을 위한 swap() 메소드를 추가했고, 코드 구현 후 문제 제출했는데 제한 시간 1초를 넘겨 계속 실패를 반복했다.

제한 시간 1초를 위해서 예외를 강제로 발생시키고, 배열 출력 시 미리 StringBuilder에 배열을 담아서 그대로 출력하는 방법으로 제한 시간 문제를 해결했다.

 

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

public class Main {
    static int cnt = 0; // 교환 횟수
    static int K; // 입력 K 값
    static boolean isSuccess = false; // 출력 성공 체크를 위한 값
    static StringBuilder sb = new StringBuilder(); // 배열 출력을 위한 StringBuilder

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

        // 배열의 크기 A와 교환 횟수 K 값 설정
        int[] inputAK = Arrays
                .stream(br.readLine().split(" "))  // 공백을 기준으로 문자열 분리
                .mapToInt(Integer::parseInt) // int형으로 형변환
                .toArray(); // 배열에 담기

        int A = inputAK[0];
        K = inputAK[1];

        // 입력 받은 배열
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] array = new int[A + 1]; // 루트 값을 index 1번으로 하기 위해서 length를 1 늘려준다
        for (int i = 1; i < array.length; i++) {
            array[i] = Integer.parseInt(st.nextToken());
        }

        try {
            heapSort(array);
        } catch (RuntimeException e) {
            System.out.println(sb); // 시간 제한 1초로 K와 cnt가 같을 때 배열 출력
        }

        if (!isSuccess) {
            System.out.println(-1); // 출력 실패 시 -1 출력
        }

        br.close();
    }

    /**
     * 원소 교환
     * @param array
     * @param a
     * @param b
     */
    static void swap(int[] array, int a, int b) {
        cnt++;

        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;

        if (cnt == K) {
            isSuccess = true;
            for (int i = 1; i < array.length; i++) {
                sb.append(array[i]).append(" ");
            }
            throw new RuntimeException(); // 강제로 예외 발생
        }
    }

    /**
     * 정렬
     * @param array
     */
    static void heapSort(int[] array) {
        buildMinHeap(array, array.length - 1);
        for (int i = array.length - 1; i > 1; i--) {
            swap(array, 1, i);
            heapify(array, 1, i - 1);
        }
    }

    /**
     * 최소 힙 생성
     * @param array
     * @param A
     */
    static void buildMinHeap(int[] array, int A) {
        for (int i = A / 2; i >= 1; i--) {
            heapify(array, i, A);
        }
    }

    /**
     * array[K]를 루트로 하는 트리를 최소 힙 성질을 만족하도록 수정
     * array[K]의 두 자식을 루트로 하는 서브 트리는 최소 힙 성질을 만족하고 있다.
     * A는 배열 Array의 전체 크기이며 최대 인덱스를 나타낸다.
     * @param array
     * @param K
     * @param A
     */
    static void heapify(int[] array, int K, int A) {
        int left = K * 2;
        int right = K * 2 + 1;
        int smaller;

        if (right <= A) {
            if (array[left] < array[right]) {
                smaller = left;
            } else {
                smaller = right;
            }
        } else if (left <= A) {
            smaller = left;
        } else {
            return;
        }

        // 최소 힙 성질을 만족하지 못하는 경우 재귀적으로 수정한다.
        if (array[smaller] < array[K]) {
            swap(array, K, smaller);
            heapify(array, smaller, A);
        }
    }
}