[백준/자바] 재귀 24060번 - 병합정렬

• 문제

N개의 서로 다른 양의 정수가 저장된 배열 A가 있다. 병합 정렬로 배열 A를 오름차순 정렬할 경우 배열 A에 K 번째 저장되는 수를 구해서 우리 서준이를 도와주자.

크기가 N인 배열에 대한 병합 정렬 의사 코드는 다음과 같다.

 

merge_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다.
    if (p < r) then {
        q <- ⌊(p + r) / 2⌋;       # q는 p, r의 중간 지점
        merge_sort(A, p, q);      # 전반부 정렬
        merge_sort(A, q + 1, r);  # 후반부 정렬
        merge(A, p, q, r);        # 병합
    }
}

# A[p..q]와 A[q+1..r]을 병합하여 A[p..r]을 오름차순 정렬된 상태로 만든다.
# A[p..q]와 A[q+1..r]은 이미 오름차순으로 정렬되어 있다.
merge(A[], p, q, r) {
    i <- p; j <- q + 1; t <- 1;
    while (i ≤ q and j ≤ r) {
        if (A[i] ≤ A[j])
        then tmp[t++] <- A[i++]; # tmp[t] <- A[i]; t++; i++;
        else tmp[t++] <- A[j++]; # tmp[t] <- A[j]; t++; j++;
    }
    while (i ≤ q)  # 왼쪽 배열 부분이 남은 경우
        tmp[t++] <- A[i++];
    while (j ≤ r)  # 오른쪽 배열 부분이 남은 경우
        tmp[t++] <- A[j++];
    i <- p; t <- 1;
    while (i ≤ r)  # 결과를 A[p..r]에 저장
        A[i++] <- tmp[t++]; 
}

 

 

 

• 풀이

재귀함수를 활용해 병합정렬을 구현했다. 재귀 함수는 귀납적으로 이해하라고들 하는데 아직 나는 익숙지 않아서 코드 흐름을 타며 이해하는 중이다. 

 

base condition을 left<right 으로 설정해 원소가 2개 남았을 때까지 재귀를 실행한다.

그리고 분할 - 병합을 반복하는데 각 루프에서 오름차순 정렬된 임시 배열의 원소들을 다시 정렬 배열에 삽입하고 해당 횟수를 카운트한다. 

카운트 수가 입력값과 일치하면 그 시점에 정렬 배열에 삽입된 숫자를 출력하고, 입력값이 총 카운트 수를 초과하면 -1를 출력한다.

 

package algorithms.recursion;

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

public class MergeSort {

    //병합정렬 : 크기 1 될 때까지 절반씩 분할 -> 인접한 숫자 비교, 정렬하면서 합쳐나감

    static int order, count;
    
    static int result = 0;

    static int numbers[], tmp[];


    public static void mergeSort(int[] numbers, int left, int right){ //병합정렬

        if (left<right) { //base condition - 원소가 2개 남을 때까지 진행
            int mid = (left + right) / 2;

            mergeSort(numbers, left, mid); //왼쪽 분할
            mergeSort(numbers, mid+1, right); //오른쪽 분할
            merge(numbers, left, mid, right); //병합
        }

    }

    public static void merge(int[] numbers, int left, int mid, int right){ //병합

        int l = left; //왼쪽정렬 시작점
        int r = mid+1; //오른쪽정렬 시작점
        int t = left; //temp 임시 배열 인덱스

        //오름차순 정렬 (한쪽 정렬 끝날 때까지)
        while (l<=mid && r<=right){
            if (numbers[l]<=numbers[r]){
                tmp[t++] = numbers[l++];
            } else {
                tmp[t++] = numbers[r++];
            }
        }

        //한쪽이 먼저 정렬 끝나면
        if (l>mid){ //왼쪽 배열 모두 정렬됐을 때 => 오른쪽 배열 남을 때
            while (r <= right){
                tmp[t++] = numbers[r++]; //남은 오른쪽 배열 원소들을 임시 배열에 모두 대입
            }
        } else { //왼쪽 배열 남을 때
            while (l <= mid) {
                tmp[t++] = numbers[l++]; //남은 왼쪽 배열 원소들을 임시 배열에 모두 대입
            }
        }

        //임시 배열 -> 정렬 배열 삽입
        for (l=left;l<=right;l++){
            ++count;
            numbers[l] = tmp[l];

            if (count==order){ //입력값 횟수만큼 배열에 저장됐을 때
                result=numbers[l];
                break;
            }

            if (order>count){ //입력값(저장 순서)이 총 저장 횟수보다 크면
                result=-1;
            }
        }

    }

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

        String input = br.readLine(); //입력값 1 : 숫자들 개수 + 저장된 순서
        String input2 = br.readLine(); //입력값 2 : 정렬할 숫자들

        StringTokenizer st = new StringTokenizer(input);
        int size = Integer.parseInt(st.nextToken()); //정렬할 숫자 개수
        order = Integer.parseInt(st.nextToken()); //배열에 저장되는 순서

        tmp = new int[size]; //임시 배열
        numbers = new int[size]; //정렬 배열

        StringTokenizer st2 = new StringTokenizer(input2);
        for (int i=0;i<size;i++) {
            numbers[i] = Integer.parseInt(st2.nextToken());
        }

        mergeSort(numbers, 0, size-1);

        System.out.println(result); //출력값 : 새 정렬 배열에 order번째 저장되는 숫자
    }

}