힙(우선순위 큐)의 활용 - BOJ 24174 알고리즘 수업 - 힙 정렬 2

문제

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

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

 

 

문제 접근

• 힙 정렬을 구현 한 후, swap 함수의 호출 카운트를 세어 그보다 작다면 -1, 같다면 해당 스왑으로 인해 바뀐 배열을 그대로 출력하면 된다.
• 차이점은 힙 정렬을 보통 최대 힙으로 구현하나 해당 문제의 의사코드는 최소 힙으로 구현하고 있다는 것이다.
• 그래도 의사코드가 세세하게 설명되어 있어 그대로 따라 구현하면 끝난다.
• 출력의 경우 배열의 길이 N이 50만이라는 큰 수이기 때문에 String을 +로 연산하면 시간초과가 나게 된다. 이를 해결하기 위해선 BufferedWriter나 StringBuilder와 같은 빠른 출력이나 문자열 연산 특화 클래스를 사용하여 출력해야 한다.

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

public class StudyCode {
    static int N;
    static int K;
    static int cnt;
    static boolean flag = false;
    static int[] data;

    static void heapSort(int[] arr){
        for (int i = arr.length / 2; i >= 1; i--){
            heapify(arr, i, N);
            if(flag){
                return;
            }
        }

        for (int i = N; i >= 2; i--){
            swap(arr, 1, i);
            heapify(arr, 1, i - 1);

            if(flag){
                return;
            }
        }
    }

    static void heapify(int[] arr, int idx, int size){
        int leftChild = idx * 2;
        int rightChild = idx * 2 + 1;
        int minIdx = 0;

        if (rightChild <= size){
            if (arr[leftChild] < arr[rightChild]){
                minIdx = leftChild;
            } else{
                minIdx = rightChild;
            }
        } else if (leftChild <= size){
            minIdx = leftChild;
        } else{
            return;
        }

        if (arr[minIdx] < arr[idx]){
            swap(arr, minIdx, idx);
            heapify(arr, minIdx, size);
        }
    }

    static void swap(int[] arr, int i, int j){
        cnt++;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;

        if (cnt == K){
            flag = true;

            StringBuilder sb = new StringBuilder();
            for (int element: data){
                if (element == -1){
                    continue;
                }
                sb.append(element);
                sb.append(" ");
            }

            System.out.println(sb.toString());
        }
    }

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

        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        data = new int[N + 1];
        data[0] = -1;

        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++){
            data[i] = Integer.parseInt(st.nextToken());
        }

        cnt = 0;
        heapSort(data);

        if (!flag){
            System.out.println("-1");
        }
    }
}