[LeetCode] Arrays101 - Merge Sorted Array

Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.

 

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

 

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

 

Constraints:

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

---

 

이 문제가 대체 뭐라고ㅠㅠ 몇 시간을 머리를 쥐어뜯으며 풀었는데 풀고나니까 너무 뿌듯해서 블로그를 안 켤 수가 없었다.

어려웠던 이유는 정렬을 in-place로 해야했기 때문이다.

 

그러니까 새로운 배열을 만들어서도 안되고, nums1 배열의 size도 늘려서는 안되고,

오로지(!) nums1 배열 안에서 알아서 잘 정렬을 해야한다는게 어려움의 포인트...

 

/**
 * @param {number[]} nums1
 * @param {number} m
 * @param {number[]} nums2
 * @param {number} n
 * @return {void} Do not return anything, modify nums1 in-place instead.
 */
var merge = function(nums1, m, nums2, n) {
    let nums2Position = 0;

    for (let i = m; i < nums1.length; i++) {
        nums1[i] = nums2[nums2Position++];
    }
    
    nums1.sort((l, r) => l - r);
};

 

물론 일단은 그냥 아몰랑~ 하면서 쉽게 쉽게 가는 방식으로 풀어봤다.

그냥 nums1 배열이랑 nums2 배열을 합친 다음에 sort 메소드로 sorting 시켜버린 것이다.

 

인생이 이렇게 쉽게만 흘러가면 얼마나 좋을까... 싶지만

문제에서 요구하는 효율적인 방식이 이게 아니란걸 알기 때문에 또 다시 고뇌의 시간 시작.

 

노트에다가 계속 썼다 지웠다하면서 이 방법 저 방법 시도해보다가 알아낸 방법은 다음과 같다.

그러니까 바로 숫자들을 뒤에서부터 비교하는 것이다! 

 

 

 

코드로 표현하면 다음과 같다!

 

var merge = function(nums1, m, nums2, n) {
    let nums1Position = m - 1;
    let nums2Position = n - 1;

    for (let i = nums1.length - 1; i >= 0; i--) {
        if (nums2Position < 0) break;
  
        if (nums1[nums1Position] > nums2[nums2Position]) {
           nums1[i] = nums1[nums1Position--];
        } else {
           nums1[i] = nums2[nums2Position--];
        }
    }
};