[ 백준 24060번 문제 ] 알고리즘 수업 - 병합 정렬 1 - JAVA

 

이번에는 백준 24060번 문제를 통해 병합 정렬 개념을 다시 다져보자.
이번 문제도 저번 개념 정리와 같이 재귀 방식으로 계속 나누고 
병합하며 정렬한다.

 

[ 알고리즘 ] 병합 정렬 - JAVA

 

🔍 문제 핵심

• 병합 정렬은 정렬 알고리즘 중 하나로, 분할 정복(Divide and Conquer) 방법을 사용한다.
• 주어진 배열을 계속해서 절반으로 나누고, 더 이상 나눌 수 없을 때까지 나눈 뒤, 정렬된 상태로 병합한다.
• 문제에서 예시로 주어진 병합 정렬 과정을 잘 이해하고, 이를 직접 구현해보는 것이 핵심이다.

📌 병합 정렬이란?

1. 분할 (Divide)

• 배열을 절반으로 나눈다.
• 이 과정을 배열의 크기가 1이 될 때까지 반복한다.
• 각 하위 배열은 재귀적으로 처리된다.

2. 정복 (Conquer)

• 크기가 1인 배열끼리 **두 개씩 병합(Merge)**하며 정렬해나간다.
• 병합 과정에서 두 배열의 원소를 비교하여 작은 값을 먼저 넣는 방식으로 정렬이 이루어진다.

3. 병합 (Combine)

• 정렬된 두 배열을 하나로 합치며 정렬을 유지한다.

 

 

 

재귀 방식으로 정렬하는 복잡한 구조로 공부하기 좋은 문제이다.
이해도를 높이기 위해 많은 관련 문제를 푸는 것을 추천한다.

전체 코드

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

public class Main {

    private static int count = 0;
    private static int number = -1;
    private static int K;

    private static void mergeSort(int[] arr, int left, int right) {
        if(left < right) {
            int mid = (left + right) / 2;

            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

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

        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1;
        int z = 0;

        while(i <= mid && j <= right) {
            if(arr[i] <= arr[j]) {
                temp[z++] = arr[i++];
            }
            else {
                temp[z++] = arr[j++];
            }

        }

        while(i <= mid) {
            temp[z++] = arr[i++];
        }

        while(j <= right) {
            temp[z++] = arr[j++];
        }


        for (int l = 0; l < temp.length; l++) {
            arr[left + l] = temp[l];
            count++;
            if(count == K) {
                number = temp[l];
            }
        }


    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        int N = Integer.parseInt(stringTokenizer.nextToken());
        K = Integer.parseInt(stringTokenizer.nextToken());

        int[] arr = new int[N];

        stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(stringTokenizer.nextToken());
        }

        mergeSort(arr, 0, N - 1);

        System.out.println(number);

    }
}