분할정복. 합병정렬

문제

합병정렬을 이해할수있는 문제. 의사 코드가 주어지고, 동작과정을 이해할수있어야한다.

해결방향성

divide : 길이가 1이될때까지 나눈다.
conquer(combine): 왼쪽, 오른쪽 두 배열로 나뉘어 수를 비교하며 임시배열에 저장 후, 원래 배열로 옮긴다.

코드

package divideAndConquer;

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

public class MergeSort {
    private static int K;
    private static int saveCount = 0;
    private static int saveNum;
    private static void mergeSort(int[] A, int left, int right) {
        if (left < right) { // start가 end보다 작으면
            int mid = (left + right) / 2; // 중간 구함. A 배열의 길이가 1이될때까지 분할(divide)
            mergeSort(A, left, mid); // 시작과 중간 머지소트. // (conquer)
            mergeSort(A, mid + 1, right); // 중간과 끝 머지소트
            merge(A, left, mid, right); // 결합 (combine)
        }
    }

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

        while (l <= mid && r <= right) { // start <= mid && mid + 1 <= end -> 두개의 배열로 나눈다고 생각하면됨.
            // A[start] <= A[mid + 1]일경우 : 각각의 첫번째 원소 비교
            if (A[l] <= A[r]){ // 첫번째 배열쪽에 있는 원소가 더 작은경우
                // tmp 임시배열에 첫번째 배열 첫원소를 넣어줌
                sorted[index] = A[l];
                index++;
                l++;
            }
            else{ // 두번째가 더 큰경우
                sorted[index] = A[r]; // 두번째 쪽을 tmp 임시배열쪽에 넣어줌
                index++;
                r++;
            }
        }
        while (l <= mid) { // 오른쪽이 먼저 채워줬을경우
            // 왼쪽거 중 남은거를 다 채워줌.
            sorted[index] = A[l];
            index++;
            l++;
        }
        while (r <= right) { // 왼쪽이 먼저 참.
            // 오른쪽 거 중 남은거를 채워줌.
            sorted[index] = A[r];
            index++;
            r++;
        }

        // 정렬된 새배열을 기존의 배열에 복사해서 옮겨줌.
        for (int i = left; i <= right; i++) {
            A[i] = sorted[i];
            saveCount++;
            if (saveCount == K) {
                saveNum = sorted[i];
            }
        }
    }

    private static int[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

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

        st = new StringTokenizer(br.readLine(), " ");

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

        mergeSort(A,0, N - 1);

        if (saveCount < K) {
            bw.write(String.valueOf("-1"));
        }
        else{
            bw.write(String.valueOf(saveNum));
        }

        bw.flush();
        br.close();
        bw.close();
    }
}

결론

사실 saveNum을 남기는 방식이 마음에 안들긴하다. 시간 복잡도를 고려해서 남겨도되는지 알아봐야할듯싶다.
참고 블로그: https://st-lab.tistory.com/233
매우 도움이 되는 블로그.