[LeetCode] 88. Merge Sorted Array (Easy) 풀이

❓ 문제

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

내림차순으로 정렬된 두 개의 정수형 배열인 nums1 및 nums2와 nums1과 nums2의 element 수를 나타내는 두 개의 정수인 m, n가 주어진다.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

nums1과 nums2를 내림차순으로 정렬된 하나의 배열로 병합하려고 한다.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

최종 정렬된 배열은 함수에 의해 반환되어서는 안되며, 대신 배열 num1 안에 저장되어야한다. 이를 수용하기 위해서는 nums1의 길이가 m + n이 되어야한다. 여기서 처음 m은 병합되어야 하는 요소를 나타내고 마지막 n은 0으로 설정되어 무시되어야 한다. nums2의 길이는 n이다.

 

Example 1:

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

Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

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

Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

 

Example 3:

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

Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

❗ 내 풀이

copy javascriptvar merge = function(nums1, m, nums2, n) {
  if(n == 0) return;

  // 불필요한 배열 요소 제거
  nums1.splice(m, nums1.length);
  nums2.splice(n, nums2.length);

  for(let i = 0; i < m + n ; i++) {
    if(nums2[0] < nums1[i]) {
      nums1.splice(i, 0, nums2[0]);
      nums2.shift(); // 제일 앞에 배열 요소 삭제
      n--;
      m++;
    }

    // nums1을 전부 비교하였음에도 nums2가 있는 경우
    // 즉 nums1의 가장 큰 수보다 nums2의 요소가 더 큰 수가 있는 경우
    if(n > 0 && m == i) {
      nums1.push(nums2[0]);
      nums2.shift(); // 제일 앞에 배열 요소 삭제
      n--;
      m++;
    }
  }
};

Runtime: 59 ms
Memory Usage: 42.1 MB

• shift() : 배열의 제일 앞부분 요소를 삭제한다.
• splice(start, deleteCount, item...) : 배열의 기존 요소를 삭제 또는 교체하거나 새 요소를 추가하여 배열의 내용을 변경한다.
  • start : 배열의 변경을 시작할 인덱스
  • deleteCount : 배열에서 제거할 요소의 수
  • item... : 배열에 추가할 요소(아무 요소도 지정하지 않으면 splice()는 요소를 제거만 한다)

 

❗ Runtime이 가장 빨랐던 답변과 비교

앞에서 비교하는 것이 아니라 뒤에서부터 비교하여 경우에 따라 배열에 넣어주었다.

copy javascriptvar merge = function(nums1, m, nums2, n) {
    m--;
    n--;
    
    let index = nums1.length - 1
    
    while(index >= 0) {
        if(m < 0) {
            nums1[index] = nums2[n--]
        } else if(n < 0) {
            nums1[index] = nums1[m--]
        } else {
            if(nums1[m] > nums2[n]) {
                nums1[index] = nums1[m--]
            } else {
                nums1[index] = nums2[n--]
            }
        }
        index--;
    }
    
    return nums1
    
};

 

❗ Memory 사용이 가장 적었던 답변과 비교

nums1과 nums2를 합쳐서 sort를 해주었다!
이렇게 간단한 방법이 있는데... 나는...ㅎㅎㅎㅎㅎ

copy javascriptvar merge = function(nums1, m, nums2, n) {
    let j=0
    for(let i=m;i<m+n;i++){
        nums1[i]=nums2[j]
        j++
    }
    return nums1.sort(function(a,b) { return a - b; });
};

 

🚩 Detail

• 날짜 : 2022.07.05
• 난이도 : Easy
• 제목 : Merge Sorted Array
• URL : https://leetcode.com/problems/merge-sorted-array/