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

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

 

 

 

이해하기

의사 코드가 있기에 그것부터 차분히 살펴봐야 했다. 일단 의사코드대로 한 번 만들어보자.

의사 코드대로 만들 수 있는 부분은 heap_sort(), build_min_heap(), heapify() 세 가지이다.

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

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

private void heapify(int[] arr, int k, int n) {
    int left = 2 * k;
    int right = 2 * k + 1;
    int smaller = 0;
    if (right <= n) {
        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);
    }
}

 

이 세 가지 함수와 더불어 swap()도 만들 수 있을 것 같다.

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[j] = arr[i];
    arr[i]= tmp;
}

 

 

 

문제 풀이

위의 함수들을 조합해서 solution을 만들어야 하는데, 일단 교환 횟수를 세기 위한 count 변수가 필요하다.

교환할 때마다 count 변수를 +1 해주면서 K랑 같아지면 예외를 발생시킨다.

private void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[j] = arr[i];
    arr[i]= tmp;
    if (++cnt == K) {
        throw new RuntimeException();
    }
}

 

solution은 try-catch문으로 작성한다.

public String solution() {
    try {
        heap_sort(arr);
    } catch (Exception e) {	// count == K 라서 RuntimeException이 발생한 경우
        return toString();	// 정렬된 배열 출력
    }
    return "-1";		// 그 외에는 -1 출력
}

 

toString()은 오버라이드한다.

@Override
public String toString() {
   StringJoiner sj = new StringJoiner(" ");
   for (int i = 1; i < arr.length; i++) {
        sj.add(Integer.toString(arr[i]));
    }
    return sj.toString();
}

 

전체적인 코드는 아래와 같다.

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

class Solution {
    int cnt = 0;
    int K;
    int[] arr;

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

    public String solution() {
        try {
            heap_sort(arr);
        } catch (Exception e) {
            return toString();
        }
        return "-1";
    }

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

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

    private void heapify(int[] arr, int k, int n) {
        int left = 2 * k;
        int right = 2 * k + 1;
        int smaller = 0;
        if (right <= n) {
            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);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[j] = arr[i];
        arr[i]= tmp;
        if (++cnt == K) {
            throw new RuntimeException();
        }
    }

    @Override
    public String toString() {
        StringJoiner sj = new StringJoiner(" ");
        for (int i = 1; i < arr.length; i++) {
            sj.add(Integer.toString(arr[i]));
        }
        return sj.toString();
    }
}

public class no_24174_re {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] arr = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        System.out.println(new Solution(arr, K).solution());
    }
}

 

 

 

의사 코드가 다 나와있는데도 처음엔 이해가 안 돼서 손도 못댔다... 이번 기회에 의사 코드를 어떻게 읽어야하는지 새로 알게 되었다.

 

나와 있는 의사 코드를 가지고 함수들을 정리해보면 생각보다 쉽게 풀리는 문제인데, 유독 어렵게 느껴졌다.

특히 try-catch문으로 count == K일 때 예외를 발생시켜 배열을 출력하고, 끝까지 예외가 발생하지 않는다면 -1을 출력하는 부분이 어려웠다. 예외를 이런 식으로 사용해 볼 생각을 못해서, 처음에는 'count > K 라면 ~ 한다.' 라는 조건을 걸었었는데 다시 생각해보니 그 부분 때문에 틀린 것 같다.

 

 

 

 

참고

[PS] 백준 24174 힙 정렬 2