[백준] 재귀 (24060 : 알고리즘 수업 - 병합정렬 1)

문제

---

https://www.acmicpc.net/problem/24060

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

---

해설

---

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

public class Main {
    static int K;
    static int res = -1;
    static int tmp[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        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());
        }
        tmp = new int[N];
        mergeSort(arr, 0, arr.length-1);
        sb.append(res);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    public 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);
        }
    }

    public static void merge(int[] arr, int left, int mid, int right) {
        int part1 = left;
        int part2 = mid+1;
        int idx = left; 
        while (part1 <= mid && part2 <= right){
            if(arr[part1] <= arr[part2]){
                tmp[idx++] = arr[part1++];
            }
            else {
                tmp[idx++] = arr[part2++];
            }
        }
        while (part1 <= mid){
            tmp[idx++] = arr[part1++];
        }
        while (part2 <= right){
            tmp[idx++] = arr[part2++];
        }
        part1 = left;
        idx = left;
        while (part1 <= right) {
            if (--K == 0){
                res = tmp[idx];
                break;
            }
            arr[part1++] = tmp[idx++];
        }
    }
}

---

main()

---

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        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());
        }
        tmp = new int[N];
        mergeSort(arr, 0, arr.length-1);
        sb.append(res);
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

메인 메서드에서, 배열을 입력받고, 이를 합병정렬을 위한 mergeSort메서드에 넘겨준다.

---

mergeSort()

---

public 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);
	}
}

mergeSort 메서드는 배열, 배열의 왼쪽, 배열의 오른쪽 인덱스를 매개변수로 받는다.

이렇게 하는 이유는 아래 그림을 통해 확인해보도록 하자.

---

(4, 5, 1, 3, 2)를 정렬해보도록 하자.

1. mergeSort 메서드를 호출한다.
2. 배열의 인덱스 반절을 다시 분할하기 위해 mergeSort()메서드를 재귀호출한다.
3. 재귀호출은 그림으로 보이는 것처럼 원소가 1개인 것으로 분할되었을 때 탈출하게 된다.
4. 이때, 박스 1개가 배열이라고 했을 때, 각 배열에 1개의 원소만 들어있을 때 이것은 정렬된 것으로 본다.
   (물리적으로 배열을 나눈 것은 아니지만, 인덱스를 통해 나눠진 것처럼 구현한 것이다.)
5. 정렬된 배열들을 합병하는 과정에서 해당 원소들을 다시 정렬하기 위해, merge 메서드를 호출한다.
6. 위의 과정을 모두 수행하고 나면, 나머지 반절을 가지고 다시 위의 과정을 진행한다.

---

merge()

---

public static void merge(int[] arr, int left, int mid, int right) {
        int part1 = left;
        int part2 = mid+1;
        int idx = left; 
        while (part1 <= mid && part2 <= right){
            if(arr[part1] <= arr[part2]){
                tmp[idx++] = arr[part1++];
            }
            else {
                tmp[idx++] = arr[part2++];
            }
        }
        while (part1 <= mid){
            tmp[idx++] = arr[part1++];
        }
        while (part2 <= right){
            tmp[idx++] = arr[part2++];
        }
        part1 = left;
        idx = left;
        while (part1 <= right) {
            if (--K == 0){
                res = tmp[idx];
                break;
            }
            arr[part1++] = tmp[idx++];
        }
    }
}

merge() 메서드는 두개의 배열을 정렬하며 합쳐주는 메서드이다.

1. part1은 왼쪽 배열, part2는 오른쪽 배열을 의미하는 것이며, 
   전체 배열의 left~mid의 인덱스는 왼쪽 배열, mid+1~right의 인덱스는 오른쪽 배열이다.
   두 배열의 값을 비교하여, 새로운 배열에 저장해주도록한다.
   
   
2. 여기서 두 배열을 비교할 때, 왼쪽, 오른쪽 배열의 범위를 넘어가면 반복문을 탈출하게 된다.
   예를들어 (4, 5), (1, 2, 3) 의 두 배열을 정렬하게 된다면  tmp = (1, 2, 3)만 저장되고, 반복문이 종료될 것이다.
   이렇게 되면, 왼쪽 배열의 4, 5는 새로운 배열에 들어가지 못하게 되므로 이를 처리해주어야 한다.
   
   
3. 따라서, 왼쪽, 오른쪽 배열에 값이 남아있다면, 이를 새로운 배열의 뒤에 붙혀준다.
   1) 뒤에 붙히는 이유 :
   이미 위에서 오름차순으로 정렬하는 과정에서 선택되지 못했기 때문에, 더 큰 값인 것이 당연하기 때문
   2) 그대로 붙히는 이유 :
   합병단계에서는 이미 정렬된 배열 2개를 가지고 합병하는 것이기 때문에 해당 배열 내부에서 다시 정렬할 필요가 없음
   
   
4. 마지막으로 새로운 배열을 기존 배열에 복사해주면 된다.

하지만, 이번 문제에서 요구하는 것은, 배열에 K번째 저장되는 수를 출력하는 것이기 때문에,
입력값 K와 결과를 저장할 res를 static으로 선언하고,
배열에 값이 저장될 때마다 1씩 빼서 0이 되는 순간 해당 값을 res에 저장한 후 출력한다.

(더 빠른 출력을 위해서 res 값을 구한 순간 더 이상의 저장은 필요가 없으므로 break를 통해 빠져나온다.) 

---

결론

---

합병정렬 알고리즘을 오랜만에 보니, 머릿속으로 어떻게 정렬이 이루어지는지는 그려지지만,

막상 코드를 작성하려니 막막하게 느껴졌었다...ㅠㅠ, 의사코드가 제공되어있어서 다행이었던 것 같다.

또한, 재귀함수는 테스트를 해볼 때 디버깅모드를 잘 사용해가면서 테스트해야, 원하는 결과가 나오지 않았을 때

과정을 하나하나 확인해보며, 해결하기 좋은 것 같다!.

---