Leetcode - 88. Merge Sorted Array - Easy

 

이번 문제는 두개의 integer array를 받고 또 두개의 숫자를 받습니다.

첫번째 배열과 첫번째 숫자의 의미는 숫자의 개수만큼 첫번째 배열의 아이템을 사용하고 나머지는 버린다 입니다.

두번째 배열과 두번째 숫자도 마찬가지 의미 입니다.

 

여기에 한가지 더 조건이 있습니다.

첫번째 배열의 아이템 숫자는 입력 받은 두 숫자의 합 이라는 겁니다.

 

이 조건 때문에 문제가 완전히 쉬워 졌습니다.

일단 첫번째 배열에서 첫번째 숫자 와 맞는 갯수 만큼만 채우고 두번째 배열에서 나머지를 그냥 채워 넣으면 되니까요. 

 

이 조건이 있는 이유는 배열은 그 크기를 변경하는 것이 불가능 하기 때문입니다.

 

크기를 변경하려면 List를 사용해야 합니다. (ArrayList, LinkedList etc.)

 

위에 얘기한 대로 코딩을 하면 아래와 같습니다.

 

참 결과 값은 정렬 되어 있어야 해서 마지막에 Arrays.sort()를 사용해야 합니다.

 

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

 

 

이렇게 하면 됩니다.

 

그런데 여기서 Arrays.sort()는 리소스를 좀 많이 차지 합니다.

좀 더 Refactoring을 하고 싶다면 아래와 같이 하면 됩니다.

 

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // Make a copy of the first m elements of nums1.
        int[] nums1Copy = new int[m];
        for (int i = 0; i < m; i++) {
            nums1Copy[i] = nums1[i];
        }

        // Read pointers for nums1Copy and nums2 respectively.
        int p1 = 0;
        int p2 = 0;
                
        // Compare elements from nums1Copy and nums2 and write the smallest to nums1.
        for (int p = 0; p < m + n; p++) {
            // We also need to ensure that p1 and p2 aren't over the boundaries
            // of their respective arrays.
            if (p2 >= n || (p1 < m && nums1Copy[p1] < nums2[p2])) {
                nums1[p] = nums1Copy[p1++];
            } else {
                nums1[p] = nums2[p2++];
            }
        }
    }
}

 

이 방법은 첫번째 배열의 뒷자리 부터 집어 넣는 것입니다.

첫번째 배열의 맨 마지막 숫자와 두번째 배열 맨 마지막 숫자를 비교해서 큰 숫자를 마지막에 넣는 것입니다.

 

하나 하나 볼까요?

 

처음에는 nums1[]을 nums1Copy[]라는 새 배열에 카피 합니다.

 

그리고 인지적 p1과 p2를 생성합니다.

 

이제 루프를 돌릴 텐데요.

m + n 만큼 돌립니다. nums1[]의 크기가 m+n이니까 첫번째 배열의 크기만큼 돌려도 됩니다.

 

If 문을 보면 p2가 n보다 크거나 같거나

p1이 m보다 작고 nums1Copy[p1] 이 nums[p2] 보다 작으면 실행합니다.

 

실행문 은 nums1[p] 에 nums1Copy[p1] 을 넣고 p1에 1을 더합니다.

 

즉 첫번째 배열의 첫번째 값이 두번째 배열의 첫번째 값보다 작으면 nums1[p]에 작은 값을 넣습니다.

반대로 else를 보면 첫번째 배열의 첫번쨰 값이 크면 두번째 배열의 첫번째 값 즉 더 작은 값을 넣습니다.

 

그 다음은 두번째 아이템으로 가서 똑 같은 일을 반복 합니다.

 

이렇게 되면 두 배열에서 작은 숫자 만큼 하나하나 채워 나가게 되므로 sorting을 할 필요가 없습니다.

 

반대로 배열의 뒤에서 부터 집어 넣을 수도 있습니다.

 

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int r1 = m-1;
        int r2 = n-1;
        
        for(int w=m+n - 1; w >= 0; w--){
            if(r1 >= 0 && r2 >= 0) {
                nums1[w] = nums1[r1] > nums2[r2] ? nums1[r1--] : nums2[r2--];
            } else if(r1 >= 0) {
                nums1[w] = nums1[r1--];
            } else {
                nums1[w] = nums2[r2--];
            }
        }
        return;
    }
}

 

이 방법은 첫번째 배열의 뒷자리 부터 집어 넣는 것입니다.

여기서는 새로운 배열을 생성하지 않고 nums1에 곧바로 값을 넣을 수 있습니다.

 

For 문은 m+n-1만큼만 돌립니다. 이 값은 w에 담깁니다.

w는 루프가 돌때마다 1식 마이너스 됩니다.

 

이것을 이용하면 nums1[]의 맨 마지막 부터 숫자를 채워 넣을 수 있습니다.

If문을 보면 r1과 r2 모두 0보다 클 경우 실행하게 되는데요.

첫번쨰 배열의 마지막에 값을 넣습니다.

그 값은 첫번째 배열 마지막 값과 두번째 배열 마지막값을 비교해서 더 큰 수를 넣고 해당 숫자 (r1 or r2)에서 1을 마이너스 합니다.

그러다가 r1이나 r2중 하나가 0보다 작게 된 경우 두번째 if로 가서 r1이 남아 있을 경우는 첫번째 배열의 r1번째 값을 넣고

r2 가 남아 있을 경우 두번째 배열의 r2값을 넣습니다.

 

이렇게 되면 배열의 뒤부터 큰 값을 채워 넣어서 나중에 정렬을 할 필요가 없어집니다.

 

 

결과를 보면 확실히 Arrays.sort()를 사용하지 않은 방법이 더 속도가 빠른것을 알 수 있습니다.

그만큼 리소스를 덜 사용하게 됩니다.