문제

https://leetcode.com/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

해결 방법 1

• 2개의 포인터를 사용하여 해결

1. nums1 배열에 사용할 포인터 idx1과 nums2 배열에 사용할 포인터 idx2 를 0으로 초기화
2. nums1[idx1]와 nums2[idx2]를 비교하여 작은 값을 result 배열에 넣어주고 넣은 값을 가리키는 idx 증가

코드

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int idx1 = 0;
        int idx2 = 0;
        int[] result = new int[m + n];

        for (int i = 0 ; i < m + n ; i ++) {
            if (idx1 == m) {
                result[i] = nums2[idx2 ++];
            } else if (idx2 == n) {
                result[i] = nums1[idx1 ++];
            } else {
                if (nums1[idx1] <= nums2[idx2]) {
                    result[i] = nums1[idx1 ++];
                } else {
                    result[i] = nums2[idx2 ++];
                }
            }
        }

        for (int i = 0 ; i < m + n ; i ++) {
            nums1[i] = result[i];
        }
    }
}

결과

해결 방법 2

• nums1 배열의 크기가 m + n으로 주어졌기 때문에 이를 활용하여 별도의 result 배열을 사용하지 않는다면 공간 복잡도를 줄일 수 있고, for문을 한 번 줄일 수 있어 시간 복잡도도 줄일 수 있음
• nums1 배열의 앞에서부터 값을 채워나가면 이미 채워져 있던 값들을 뒤로 옮기는 작업이 추가되기 때문에 시간 복잡도가 증가 => 뒤에서부터 채우면 됨

코드

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int idx = m + n - 1;
        m --;
        n --;

        while (idx >= 0) {
            if (m < 0) {
                nums1[idx --] = nums2[n --];
            } else if (n < 0) {
                nums1[idx --] = nums1[m --];
            } else {
                if (nums1[m] > nums2[n]) {
                    nums1[idx --] = nums1[m --];
                } else {
                    nums1[idx --] = nums2[n --];
                }
            }
        }
    }
}

결과