[JAVA] 병합 정렬 개념 및 알고리즘을 이용한 코딩#2

병합 정렬 개념

병합 정렬은 여러 개의 정렬된 자료의 집합을 결합해 하나의 집합으로 만드는 정렬 방법이다. 이 정렬은 전체를 상대로 수행하지 않고 분할(Divide)한 뒤 각 부분집합들에 대해 정렬한 후 다시 결합(Combine)하는 분할 정복(Divide and Conquer) 기법을 사용한다.

분할 정복법(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발하였다. 대표적으로는 퀵소트 나 합병정렬이 있다.

매일프로그래밍 문제 기준

1. 문제
   사이즈가 m인 배열 X와 사이즈가 n인 배열 Y가 주어집니다. 두 배열은 모두 정렬된 상태입니다.
   배열 X에는 정확히 n개의 비어있는 셀이 있다고 할 때, 배열 Y의 원소를 X 배열로 합치며 원소들을 정렬 시키시오.

Input
X = [0, 2, 0, 3, 0, 5, 6, 0, 0] (비어있는 셀은 0으로 표현되었음)
Y = [1, 8, 9, 10, 15]

Output
X = [1, 2, 3, 5, 6, 8, 9, 10, 15]

2. 풀이
   문제를 쉽게 풀어보았습니다. 우선 0의 값을 앞쪽으로 모두 정렬 시킵니다. Arrays.sort(x) -> {0, 0, 0, 0, 0, 2, 3, 5, 6} 그리고 나서 0인 값들을 비교하여 그방안에 Y의 원소값을 넣고 나서 다시한번 Arrays.sort 함수를 사용하하여 쉽게 문제를 풀어보았습니다. 이렇게 풀어도 되는건진 모르겠습니다.

import java.util.Arrays;

class Merge
{

    public static void main (String[] args)
    {
        int[] X = { 0, 2, 0, 3, 0, 5, 6, 0, 0};
        int[] Y = { 1, 8, 9, 10, 15 };

        merge(X, Y);
        //result
        System.out.println(Arrays.toString(X));
    }

    private static void merge(int[] x, int[] y) {
        //x의 값을 sort 함수를 통해 {0, 0, 0, 0, 0, 2, 3, 5, 6} 값이 나오도록 합니다.
        Arrays.sort(x);

        Y값을 루프를 돌면서 x의값의 위치는 y의값과 동일하기 때문에 y의값 그대로 x에 넣어줍니다.
        for (int i = 0; i < y.length; i++) {

            if(x[i] == 0) {
                x[i] = y[i];
            }
        }
        //다시 sort 하면 x의값 방에는 rsult값이 나타납니다.
        Arrays.sort(x);
    }
}

결과