BOJ_24060 : 알고리즘 수업 - 병합 정렬 1

👉 문제링크

24060번: 알고리즘 수업 - 병합 정렬 1

---

---

🔸 문제 분석 🔸

• 주어진 의사 코드로 병합 정렬을 구현한다.

🔸 코드 🔸

import java.util.Scanner;

public class Main {
    static int count, num;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();

        num = k;
        int[] a = new int[n];
        int[] tmp = new int[n+1];

        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        merge_sort(a, 0, n - 1, tmp);

        if (count < k) {
            System.out.println(-1);
        } else {
            System.out.println(num);
        }
    }

    private static void merge_sort(int[] a, int p, int r, int[] tmp) {
        if (p < r) {
            int q = (p + r) / 2;
            merge_sort(a, p, q, tmp);
            merge_sort(a, q + 1, r, tmp);
            merge(a, p, q, r, tmp);
        }
    }

    private static void merge(int[] a, int p, int q, int r, int[] tmp) {
        int i = p, j = q + 1, t = 1;

        while (i <= q && j <= r) {
            if (a[i] <= a[j]) {
                tmp[t++] = a[i++];
            } else {
                tmp[t++] = a[j++];
            }
        }
        while (i <= q) {
            tmp[t++] = a[i++];
        }
        while (j <= r) {
            tmp[t++] = a[j++];
        }
        i = p;
        t = 1;
        while (i <= r) {
            a[i++] = tmp[t++];
            if (++count == num) {
                num = tmp[t - 1];
            }
        }
    }
}

🔸 코드 해석 🔸

• main 메서드는 입력 값 저장과 의사코드로 구현한 메서드를 호출하고 결과를 출력한다.
• merge_sort 메서드에서 시작 인덱스 p, 끝 인덱스 r의 중간 값으로 q를 계산한다.
• 다시 p~q, q+1~r 각각 merge_sort를 다시 돌린다.(재귀)
  • p가 r이상이 되면 재귀를 종료한다.
  • merge_sort 2번 후 merge메서드에서 병합을 실행한다.
    • 두 범위를 arr에 합쳐 넣으면서, 작은걸 먼저 넣는 방식으로 정렬이 이루어 진다.

---

🔸 end 🔸

• 의사 코드에 tmp 선언이 빠져있어서 병합 정렬의 개념을 다시 찾아보았다. (포스팅)