백준 25174 문제 풀이

문제링크: https://www.acmicpc.net/problem/24174

사용한 자료구조: 힙(최소 힙)

문제에서 힙소트를 하고 있으므로 힙을 사용하여 문제를 해결한다.

발견한 규칙

그냥 문제에서 주어진 수도코드를 자바 코드로 작성해서 문제를 해결한다. swap을 해줄때 마다 count변수를 하나씩 증가시킨다.

코드 및 코드 설명

import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n, k;
        n = sc.nextInt();
        k = sc.nextInt();
        int[] arr = new int[n+1];
        for(int i = 1; i<=n; i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(new Solution(n,k, arr).solution());
    }

    static class Solution{
        int k;
        int n;
        int[] arr;

        public Solution(int n, int k, int[] arr) {
            this.n = n;
            this.k = k;
            this.arr = arr;
        }

        int count = 0;

        public String solution(){
            try{
                heap_sort(arr); // 힙 소트를 진행한다.
            } catch (Exception e){
                return toString(); // 만약 k만큼 교환했다면 교환 결과를 반환한다.
            }
            return "-1"; // 교환횟수가 k보다 작다면 -1를 반환한다.
        }

        void heap_sort(int[] arr){
            buildMinHeap(arr, n); 
            for(int i= n; i>=2; i--){
                swap(arr, 1, i);
                heapify(arr, 1, i-1);
            }
        }

        void buildMinHeap(int[] arr, int n){
            for(int i = n/2; i>=1; i--){
                heapify(arr, i, n);
            }
        }

        void heapify(int[] arr, int k, int n){ // 최소힙의 성질을 만족하기위해 교환하는 작업을 진행핸다.
            int left = 2*k;
            int right = 2*k +1;
            int smaller = 0;
            if(right <= n) { // 만약 자식노드가 2개라면
                if(arr[left] < arr[right]){ // 왼쪽 자식 노드가 더 작을 때
                    smaller = left; 
                } else { // 오른쪽 자식 노드가 더 작을 때
                    smaller = right;
                }
            } else if(left<=n){ // 자식 노드가 한개라면
                smaller = left; 
            } else {
                return;
            }

            if(arr[smaller] < arr[k]){ // 현재노드보다 자식 노드가 더 작을때
                swap(arr, smaller, k); // 교환해서 최소힙 성질을 만족시켜준다.
                heapify(arr, smaller, n); 
            }
        }

        void swap(int[] arr, int i, int j){
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            count+=1; // 교환한 횟수를 늘린다.
            if(count == k) throw new RuntimeException(); // 만약 교환횟수가 k와 같다면 에러를 반환해 힙소트 과정을 멈춘다.
        }

        @Override
        public String toString() {
            StringJoiner sj = new StringJoiner(" "); // " "를 추가하는 string 사이에 넣어준다.
            for(int i = 1; i<arr.length; i++){
                sj.add(Integer.toString(arr[i]));
            }
            return sj.toString();
        }
    }
}

시행착오 및 교훈

그냥 수도코드를 자바 코드로 옮겨서 풀었다. 힙소트에 대해 학습하고 나면 보다 더 이해할 수 있을것 같다!
수도코드를 코드로 옮기는것도 쉽지 않음을 느꼈다.. 꾸준히 알고리즘과 자료구조 공부를 해서 익숙하게 만들어 내것을 체화해야겠따!