88. Merge Sorted Array

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문제 출처

Merge Sorted Array - LeetCode

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109<= nums1[i], nums2[j] <= 109

[문제를 풀기 전에 생각해야 될 예외들]

1.배열들의 포인터가 배열의 크기를 벗어나면 안됨.

2.nums2의 크기(n)가 0일 수도 있습니다.

3.값이 0일 경우 대소 관계에서, 빈 자리여서 0인지 아니면 그냥 값이 0인지 차이를 알아야함.

 

[처음 생각한 접근 방법]

 

첫번째 방법

nums1에 0이 있는 곳에 nums2 요소들을 넣기.

 

주어진 배열 1,2,3,0,0,0과 2,5,6이 있습니다.

 

0에 자리에 num2의 요소들을 넣습니다.

 

nums1 배열을 정렬합니다.

 

import java.util.Arrays;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = 0;
        while (n-- > 0) {
            nums1[m+i] = nums2[nums2.length-n-1];
            i++;
        }

        Arrays.sort(nums1);
    }
}

두번째 방법

앞에서부터 더 작은 수면 배열의 모든 요소들을 한 칸 뒤로 미루고 숫자를 넣는다.

nums1과 num2의 대소를 비교합니다. nums2가 크므로 아무 것도 하지 않고 nums1의 포인터를 2로 이동합니다.

 

대소 비교합니다. nums1이 nums2보다 크지 않으므로 포인터 이동합니다.

 

 

nums2가 더 작습니다. 

 

nums1의 요소들을 한칸씩 전진합니다.

 

3이 오른쪽으로 이동했으므로 빈자리가 된 곳에nums2의 요소를 넣습니다.

나머지 5와 6은 무조건 바꿔야 하는 수이므로 차례대로 넣어줍니다.

무조건 바꿔야 하는 이유는 배열을 서로 바꿔야 하는 횟수가 m회입니다.(이 테스트케이스의 경우 3회)

 

앞에서 한번 바꿨으므로 남은 바꿔야 하는 횟수는 2회

남은 배열의 개수가 2개이므로 

나머지 숫자 2개는 무조건 들어가야합니다.

 

6도 마저 넣습니다.

 

 

끝

 

 

import java.util.Arrays;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {

        //{1} {}
        int nums1Pointer = 0;
        int nums2Pointer = 0;
        int swipedEndPoint = m;
        while (nums1Pointer <= nums1.length-1 && nums2Pointer <= nums2.length-1) {
            //nums2[nums2Pointer] < nums1[nums1Pointer]이면
            //
            if (nums2[nums2Pointer] < nums1[nums1Pointer] || nums1Pointer >= m) {
                //nums2를 넣게 nums1을 한칸씩 뒤로 땡긴다.
                swipeArrays(nums1Pointer,m++, nums1);
                //nums2를 nums1[nums1Pointer]에 넣는다.
                nums1[nums1Pointer] = nums2[nums2Pointer];
                //nums1Pointer를 한칸 뒤로 미룬다.
                nums1Pointer++;
                //nums2Pointer를 한칸 뒤로 미룬다.-> 이 수는 이미 nums1에 들어갔으므로.
                nums2Pointer++;
            } else {
                //nums1 < nums2일 때.
                //nums2가 nums1[nums1Pointer]보다 크므로, nums1Pointer를 한 칸 뒤로 미룬다. (nums2Pointer를 미뤄봤자.
                //증가순이므로 영원히 nums2가 nums1보다 커지니까 nums1pointer를 증가시켜야함.
                nums1Pointer++;
            }
        }
    }

    public void swipeArrays(int swipedStartPoint,int swipedEndPoint, int[] array) {
        while (swipedStartPoint <= swipedEndPoint) {
            //만약 마지막 값이면, 값을 미는 게 아니라 그냥 포인터만 감소해야함.
            if (swipedEndPoint != array.length - 1) {
                array[swipedEndPoint+1] = array[swipedEndPoint];
            }
            swipedEndPoint--;
        }
    }
}

[리팩토링]

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int nums1Pointer = 0;
        int nums2Pointer = 0;

        while (nums1Pointer <= nums1.length-1 && nums2Pointer <= nums2.length-1) {
            if (nums2[nums2Pointer] < nums1[nums1Pointer] || nums1Pointer >= m) {
                swipeArrays(nums1Pointer,m++, nums1);
                nums1[nums1Pointer] = nums2[nums2Pointer++];
            }
            nums1Pointer++;
        }
    }

    public void swipeArrays(int swipedStartPoint,int swipedEndPoint, int[] array) {
        while (swipedStartPoint <= swipedEndPoint) {
            if (swipedEndPoint != array.length - 1) {
                array[swipedEndPoint+1] = array[swipedEndPoint];
            }
            swipedEndPoint--;
        }
    }
}

 

[리트코드 답안]

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int tail1 = m - 1, tail2 = n - 1, finished = m + n - 1;
    while (tail1 >= 0 && tail2 >= 0) {
        nums1[finished--] = (nums1[tail1] > nums2[tail2]) ? 
                             nums1[tail1--] : nums2[tail2--];
    }

    while (tail2 >= 0) { //only need to combine with remaining nums2
        nums1[finished--] = nums2[tail2--];
    }
}

 

나의 경우에는 앞에서부터 정렬했는데.

위의 방법은 뒤에서부터 큰 수를 두는 방식으로 한 거 같다. 이렇게하면 뒤로 미루는 과정도 필요 없어진다.

아주 좋은 코드 같다.

투포인터라는 문제 출제 의도에도  맞는 좋은 방법 같다.

훨씬 깔끔하고 빠르고 좋다.