[array] merge sorted array

✅ Problem

https://leetcode.com/problems/merge-sorted-array/description/

 

✅ Approach & Solution

공통 : 투 포인터 사용

 

방식1) 작은 원소부터 넣기 (추가 공간 사용)

• 정답값을 담을 추가 배열(result)을 선언해 작은 원소부터 넣음
• 문제 조건에서 nums1 배열에 값을 담으라고 했으므로 추가 배열(result)에 저장된 값들을 nums1 배열로 옮김
  • nums1 배열은 m + n 개의 원소를 담을 수 있음

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

        int p1 = 0, p2 = 0, p3 = 0;
        while (p1 < m && p2 < n) {
            if (nums1[p1] < nums2[p2]) {
                result[p3] = nums1[p1];
                p1++;
            } else {
                result[p3] = nums2[p2];
                p2++;
            }

            p3++;
        }

        // 남은 숫자 처리
        while (p1 < m) {
            result[p3] = nums1[p1];
            p1++;
            p3++;
        }

        while (p2 < n) {
            result[p3] = nums2[p2];
            p2++;
            p3++;
        }

        // num1에 결과 넣기
        for (int i = 0; i < m + n; i++) {
            nums1[i] = result[i];
        }
    }
}

 

방식2) 큰 원소부터 넣기

• 큰 원소부터 넣을 경우 nums1 배열의 마지막 index부터 채워지기 때문에 추가 배열을 사용하거나 nums1 배열의 원소를 뒤로 밀지 않아도 됨

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

        while (nIdx >= 0) {
            if (mIdx >= 0 && nums1[mIdx] > nums2[nIdx]) {
                nums1[right] = nums1[mIdx];
                mIdx--;
            } else {
                nums1[right] = nums2[nIdx];
                nIdx--;
            }
            right--;
        }
    }
}