반응형
블로그 이미지
개발자로서 현장에서 일하면서 새로 접하는 기술들이나 알게된 정보 등을 정리하기 위한 블로그입니다. 운 좋게 미국에서 큰 회사들의 프로젝트에서 컬설턴트로 일하고 있어서 새로운 기술들을 접할 기회가 많이 있습니다. 미국의 IT 프로젝트에서 사용되는 툴들에 대해 많은 분들과 정보를 공유하고 싶습니다.
솔웅

최근에 받은 트랙백

글 보관함

Leetcode - 88. Merge Sorted Array - Easy

2022. 9. 7. 05:37 | Posted by 솔웅


 

이번 문제는 두개의 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()를 사용하지 않은 방법이 더 속도가 빠른것을 알 수 있습니다.

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

 

반응형

Comment