문제 정보

문제 요약

두 개의 정렬된 정수 배열 num1과 nums2가 주어졌을 때 이를 nums1 하나의 배열로 병합해라.

nums1과 nums2의 배열 m개와 n개가 정렬된 상태이다. nums1 배열은 nums2의 n개를 저장하기에 충분한 공간이 있다고 가정한다.

제약 사항

• 0 <= n, m <= 200
• 1 <= n + m <= 200
• nums1.length == m + n
• nums2.length == n
• -10^9 <= nums1[i], nums2[i] <= 10^9

접근 방법

문제에서 두 배열이 정렬된 상태라는 것이 가장 중요한 정보다. 따라서 가장 큰 수부터 작은 수로 내려가면서 nums1 배열의 저장된 위치에 nums2의 배열값을 저장하면 nums1로 병합할 수 있다.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        
        if (m == 0){
        	// nums1에 저장된 수가 없다면
            nums1 = nums2;
            return;
        }
        
        if (n == 0){
        	// nums2에 저장된 수가 없다면
            return;
        }
        
        while (i >= 0 && j >= 0){
            if (nums1[i] > nums2[j]){
            	// nums1이 nums2보다 크다면
                // nums1의 i번째 수의 위치는 i +j + 1이 된다.
                // +1을 하는 이유는 초기값 2개를 더했을 때 m + n -1 이 되어야 하기 때문에 조금만 더 생각하면 된다.
                nums1[i+j+1] = nums1[i];
                // nums1[i] 위치에는 nums2[j]가 위치해야 한다.
                nums1[i] = nums2[j];
                i--;
            }else{
            	// nums2[j]가 nums1[i+j+1]로 가야 한다.
                nums1[i+j+1] = nums2[j];
                j--;
            }
        }
        
        while (j >= 0){
        	// nums1 = [4,5,6, 0, 0, 0] , nums2 = [1,2,3]일 때
            nums1[j] = nums2[j];
            j--;
        }
    }
};