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

 

목차

 

---

📢 문제 출처

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

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

---

📢 문제 설명

---

📢 입출력 예시

---

📢 문제 풀이

• 문제 예시에 Heap을 정렬할 수 있는 의사 코드가 있다.
• heap_sort, build_min_heap, heapify 함수를 코드적으로 컨버팅하여 프로젝트에 삽입한다.
• 입력한 'K' 와 진행한 카운트가 같으면 교환했던 배열을 한 줄로 출력한다.
• 반면에 입력한 'K' 보다 교환 횟수가 작으면 -1을 출력해야한다.(입력 값으로 받은 카운트를 static 으로 선언)
• heapify 코드 진행 시에 자식 노드 인덱스를 구할 시에 인덱스를 1로 해야하는 경우로 구해졌기 때문에 인덱스를 1로 설정한다. (Heap의 부모/자식 노드 찾기)

 

---

📢 코드

import javax.swing.plaf.synth.SynthUI;
import java.io.*;
import java.util.StringTokenizer;

public class Q24174 {
    public static boolean isOut = false;
    public static int swapCnt = 0;   //값 스왑할 때마다의 카운트
    public static int target = 0;

    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());   //배열의 크기
        target = Integer.parseInt(st.nextToken());   //교환 횟수

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

        heap_sort(arr);
        if (!isOut) {
            System.out.print(-1);
        }
    }

    public static void heap_sort(int[] arr){
        build_min_heap(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 build_min_heap(int[] arr, int n){
        for (int i = n / 2; i > 0; i--) {
            heapify(arr, i, n);
        }
    }

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

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

        //최소 힙 성질을 만족하지 못하는 경우 재귀적으로 수정한다.
        if(arr[smaller] < arr[k]){
            swap(arr, k, smaller);
            heapify(arr, smaller, n);
        }
    }
    public static void swap(int[] arr, int a, int b) {
        //값 스왑하기
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;

        swapCnt++; 
        if(swapCnt == target)
        {
            //swapCnt가 target이 되면 result 문자열에 지금 배열 삽입
            StringBuilder sb = new StringBuilder();
            for(int i = 1; i< arr.length; i++){
                sb.append(arr[i]+" ");
            }
            System.out.print(sb.toString());
            isOut = true;
        }
    }
}

---