[Java] 백준 24060번: 알고리즘 수업 - 병합 정렬1

문제 url
알고리즘 수업 - 병합 정렬1

문제

🤔 문제 알아보기

---

문제자체는 제목과 똑같이 병합 정렬을 이용해서 푸는 것이다.
필자는 해당 문제를 풀고자 병합 정렬을 정리해봤고.. (이거 정리하고 이해하고 체화시킨다고 하루를 쓴것 같다.)

그것을 바탕으로 풀었다. 병합 정렬에 대해서는 특별한 설명없이 아래 링크를 통해 원리를 이해하면 좋다.
[정렬] Java 병합 / 합병 정렬 (Merge Sort)

그럼 문제를 풀어보겠다.

🐱‍👤 실제 코드

---

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int temp[];
    static int cnt;
    static int K;
    static int K_value;
    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());
        K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        merge_sort(arr);

        if(K_value >0) {
            System.out.println(K_value);
        } else {
            System.out.println(-1);
        }

    }

    public static void merge_sort(int[] arr) {
        temp = new int[arr.length];
        merge_sort(arr, 0, arr.length -1);

        // 다쓴 temp 배열을 GC에서 처리시키기 위해
        temp = null;
    }

    private static void merge_sort(int[] arr, int left, int right) {

        if(left == right) {
            return;
        }

        int mid = (left + right) / 2;

        merge_sort(arr, left, mid);
        merge_sort(arr, mid+1, right);

        merge(arr, left, mid, right);
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int l = left;
        int r = mid + 1;
        int idx = left;

        while(l <= mid && r <= right) {
            if(arr[l] <= arr[r]) {
                temp[idx] = arr[l];
                idx++;
                l++;
            }
            else {
                temp[idx] = arr[r];
                idx++;
                r++;
            }
        }

        // 잔여 요소 채워넣기

        // 오른쪽 배열 남은 요소 채워넣기
        if(l > mid) {
            while(r <= right) {
                temp[idx] = arr[r];
                idx++;
                r++;
            }
        }
        // 왼쪽 배열 남은 요소 채워넣기
        else {
            while(l <= mid) {
                temp[idx] = arr[l];
                idx++;
                l++;
            }
        }

        for(int i = left; i <= right; i++) {
            cnt++;
            if(cnt == K) {
                K_value = temp[i];
                break;
            }
            arr[i] = temp[i];
        }
    }
}

병합정렬을 사용한다면 특별히 어려운 것 없이, 마지막 병합과정에서
현재 저장되는 개수가 입력받은 저장 개수와 일치할 때 해당 값을 변수에 담으면 된다.

그러한 작업으로 cnt(저장되는 수)와 K_value(입력받은 값과 일치할 때, 정렬될 값)을 static으로 지정하였으며,
K(입력받을 값) 역시 마지막 병합 과정에서 쓰이기 때문에 따로 static으로 지정해 전역적으로 사용할 수 있도록 하였다.

😒 회고

---

해당 문제를 bottom up(재귀를 사용하지 않는)방식으로 풀었는데, 문제가 풀리지 않았다. 그래서 열심히 코드를 살펴보니~ 필자가 오타낸 것과 잘못 이해한 부분이 있어 이를 고쳤는데

왜 고쳐도 해결이 되지 않을까... 했는데, 해당 카테고리가 재귀파트라서 bottom up 방식이 아닌 top-down(재귀를 사용하는)으로 해야 하는 것인가 해서 top-down 방식으로 하니 풀었다.

이러면서 아~ 작동 원리가 다르기 때문에 배열에 담기는 순서도 다른 것을 참으로 늦게도 알아 차렸다.
하지만!! 바보같은 생각 덕분에 다시금 bottom up 방식을 수정할 수 있었고 좀 더 보완해볼 수 있었다.

아래는 bottom up방식으로 구현한 코드이다.
정렬 방법은 같으나, 해당 코드로는 오답이다.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static int temp[];
    static int cnt;
    static int K;
    static int K_value;
    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());
        K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        merge_sort(arr);

        System.out.println(Arrays.toString(arr));

        if(K_value >0) {
            System.out.println(K_value);
        } else {
            System.out.println(-1);
        }

    }

    public static void merge_sort(int[] arr) {
        temp = new int[arr.length];
        merge_sort(arr, 0, arr.length -1);

        // 다쓴 temp 배열을 GC에서 처리시키기 위해
        temp = null;
    }

    private static void merge_sort(int[] arr, int left, int right) {
        for(int size = 1; size <= right; size = 2 * size) {
            for(int l = 0; l <= right - size; l += (2 * size)) {
                int low = l;
                int mid = l + size - 1;
                int high = Math.min(l + (2 * size) - 1, right);

                merge(arr, low, mid, high);


            }
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int l = left;
        int r = mid + 1;
        int idx = left;

        while(l <= mid && r <= right) {
            if(arr[l] <= arr[r]) {
                temp[idx] = arr[l];
                idx++;
                l++;
            }
            else {
                temp[idx] = arr[r];
                idx++;
                r++;
            }
        }

        // 잔여 요소 채워넣기

        // 오른쪽 배열 남은 요소 채워넣기
        if(l > mid) {
            while(r <= right) {
                temp[idx] = arr[r];
                idx++;
                r++;
            }
        }
        // 왼쪽 배열 남은 요소 채워넣기
        else {
            while(l <= mid) {
                temp[idx] = arr[l];
                idx++;
                l++;
            }
        }

        for(int i = left; i <= right; i++) {
            cnt++;
            if(cnt == K) {
                K_value = temp[i];
                break;
            }
            arr[i] = temp[i];
        }
    }
}