[leetCode 88 번] Merge Sorted Array (Java)

1. 문제

---

Merge Sorted Array - LeetCode

Merge Sorted Array - LeetCode

 

---

2. 문제 설명

-  문제에서 2개의 배열과 2개의 변수가 주어진다 (nums1, nums2 ) (m , n) 이 주어진다.

-  이 두개의 배열은 오름차순으로 정렬되어있다.

-  (핵심) nums1 배열에 nums2 배열을 병합하는데, 병합 후 모든 원소가 오름차순 정렬 되어야 한다.

 

- 문제에서 병합의 길이는 m+n의 길이를 갖는다.

- 변수 m 은 num1 의 추가할 수 있는 공간

- 변수 n 은 num2 의 배열의 길이(갯수)를 의미한다.

 

---

3. 내 소스 코드(Java)

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
       if(m>0 && m+n >= m) {
            for (int i = m; i < nums1.length; i++) {
                nums1[i] = nums2[i - m];
            }
            int [] copy = new int[nums1.length];
            mergeSort(nums1,copy,0,nums1.length-1);
            System.out.print(Arrays.toString(nums1));
        }else{
            for(int i=m; i< nums1.length; i++){
                nums1[i] = nums2[i];
            }
            System.out.print(Arrays.toString(nums1));
        }
    }
    public static void mergeSort(int[] arr , int[] copy,int left , int right){
        if(left < right){
            int mid = (left + right) / 2;
            mergeSort(arr,copy,left,mid);
            mergeSort(arr,copy,mid+1, right);
            sorting(arr,copy,left,right,mid);
        }
    }
    public static void sorting(int[] arr, int[] copy, int left, int right, int mid){
        int p1 = left;
        int p2 = mid + 1;
        int idx = p1;

        while(p1<=mid || p2<= right){
            if(p1 <= mid && p2 <= right){
                if(arr[p1] <= arr[p2]){
                    copy[idx++] = arr[p1++];
                }else{
                    copy[idx++] = arr[p2++];
                }
            }else if (p1<=mid && p2 > right){
                copy[idx++] = arr[p1++];
            }else{
                copy[idx++] = arr[p2++];
            }
        }
        for (int i = left; i <=right ; i++) {
            arr[i] = copy[i];
        }

    }
}

 

---

4. 문제 해설

 

1.  문제에서 병합의 길이는 m+n의 길이를 갖는다. 라는 조건과 , 변수 m 은 num1 의 추가할 수 있는 공간 오름차순 되어있다. 라는 조건을 생각 해봤을 때 nums1 에 m부터 시작하여 추가 할 수 있는 공간에 nums2 를 for문으로 삽입을 진행해 주면 정렬이 되지않은 nums1+nums2 배열이 완성 된다. 

 

1-1. m<0 추가 할 수 있는 공간이 없거나 nums2 배열이 비어있을 경우를 생각하여 else 문을 작성. 하여 nums1 을 만들어준다, 

 

2. nums1[] = nums1+nums2 이 완성 되면 copy 배열을 새로 new해서 nums1의 길이로 할당 해준다.

 

3. 정렬을 실행해 준다.

 

3-1. 정렬은 MergerSort Alogrigthm을 사용 하여 정렬을 진행한다. mergerSort(정렬할배열, 결과배열, left , right) 함수를 작성

 

3-2 . mergeSort 메소드는 재귀 를 통해 mid 값을 구하고 계속 자르면서 merge 할 왼쪽 / 오른쪽을 구분 

 

3-3 .

int mid = (left + right) / 2;
mergeSort(arr,copy,left,mid); // 좌측
mergeSort(arr,copy,mid+1, right); // 우측

sorting(arr,copy,left,right,mid);

왼쪽과 오른쪽 을 구분 후 작성한 sorting 메서드를 호출하여 정렬을 진행한다.

 

4.재귀를 돌면서 p1 과  p2 를 왼쪽과 중앙+1 로 잡은뒤 정렬을 진행한다.

 

4-1.

if(arr[p1] <= arr[p2])

정렬을 왼쪽이 오른쪽 보다 작을경우 스왑

else if (p1<=mid && p2 > right)

반대일 경우 정렬

for (int i = left; i <=right ; i++) {
    arr[i] = copy[i];
}

분리되어 정렬된 것을 copy배열에 집어넣어 다시 재귀.

---

5.결과 

---

6. 다른 사람 소스코드

 

public void merge(int[] nums1, int m, int[] nums2, int n) {
   if (m + n > m) {
      for (int i = m; i < m + n; i++) {
         nums1[i] = nums2[i - m];
      }
   }
   Arrays.sort(nums1);
}

---

위에 조건 과 for문은 거의 똑같이 작성했다.. 그 이후 정렬을 라이브러리를 통해 정렬을 한 것 같다.

 

이 문제는기본적으로 기본적인 배열의 병합과 정렬을 하려는 문제였던것 같다. 

 

문제를 너무 어렵게 접근 한 것 같다.