[LeetCode] Merge Sorted Array - Javascript

Merge Sorted Array

[정렬된 두개의 배열을 합쳐서 하나의 정렬된 배열 만들기]

 

제약 조건 

nums1.length == m + n

nums2.length == n

0 <= m, n <= 200

1 <= m + n <= 200

-109 <= nums1[i], nums2[j] <= 109

 

Example

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

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

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

초기 문제 접근 방식

nums1 배열에 nums2 배열을 병합 한 후 병합 한 배열에 "0" 인 값이 존재 하면,

해당 배열의 인덱스를 삭제하고 해당 배열을 오름차순을 하여 문제를 풀면 되겠다 라며 생각을 했다.

 

먼저 nums1와 nums2 배열을 병합을 하는 작업을 하고,

// nums1배열에 nums2 배열 병합
nums1.push(...nums2);

 

병합된 nums1 배열의 길이만큼 for 문을 실행하며 nums1 배열 인덱스의 값이 "0"이라면 인덱스 삭제했다.

// 병합된 nums1 배열의 길이만큼 for 문을 실행하며 nums1 배열 인덱스의 값이 "0"이라면 인덱스 삭제
for(let i = 0; i < nums1.length; i++) {
      if (nums1[i] === 0) {
         nums1.splice(i, 1);
         i--;
      }
   }
   
 // nums1 배열 오름차순 정렬
 nums1.sort(function (a, b) {
     return a - b;
 });

 

초기 전체코드

/*
* @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) {
   nums1.push(...nums2);
   for (let i = 0; i < nums1.length; i++) {
      if (nums1[i] === 0) {
         nums1.splice(i, 1);
         i--;
      }
   }
   nums1.sort((a,b) => a-b);
};

 

해당 코드로 주어진 아래의 testcase 3개를 모두 통과하여 제출을 했다.

ex1) input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
ex2) input: nums1 = [1], m = 1, nums2 = [], n = 0
ex3) input: nums1 = [0], m = 0, nums2 = [1], n = 1

다시 생각 해보며..

하지만 전체의 59개의 testcase 중 24개밖에 통과를 하지 못했고, 해당 코드에 문제가 있음을 인지했다.

먼저 실패한 testcase는 아래와 같다.

ex4) input: nums1 = [-1,0,0,3,3,3,0,0,0], m = 6, nums2 = [1,2,2], n = 3

그렇다.. 위의 테스트 케이스처럼 배열의 값 중 "0"을 가진 인덱스를 모두 삭제해야 할 게 아닌,

m의 값이 6이라면, nums1에는 6개의 정수가 있다는 의미이고 [-1,0,0,3,3,3] 을 제외한 뒤에 오는 [0,0,0] 3개를 삭제 해야 한다.

 

재풀이하며 우선 nums1와 nums2를 먼저 병합하는게 아닌 nums1의 배열을 정리하고 병합해야겠다고 생각했다.

nums2에는 어떤 값이 들어오든 삭제해야 할 인덱스가 없기 때문이다.

m은 nums1 배열이 가진 정수의 개수를 의미한다.

반복문이 m부터 시작하게 하여 nums1 배열의 값이 "0"이라면 해당 인덱스를 삭제한다.

정리된 nums1 배열과 nums2를 병합 후 오름차순으로 정렬하면 해당 문제의 testcase를 모두 통과 할 수 있었다.

solve 전체 코드

/**
 * @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) {
   for (let i = m; i <= nums1.length; i++) {
      if (nums1[i] === 0) {
         nums1.splice(i, 1);
         i--;
      }
   }
   nums1.push(...nums2);
   nums1.sort((a,b) => a-b);
};

 

다른 sovle 코드

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--];
      }
   }
};

 

투포인터 방식으로도 풀이가 가능하다.

nums1Postion과 nums2Postion을 각각 배열의 마지막 인덱스을 가르키게 값을 초기화 하고,

 

nums1의 배열을 역순으로 순회하며 nums1[nums1Position]과 nums2[nums2Position]를 비교한다.

nums1의 값이 더 크다면 nums1[i]의 현재위치에 nums1[nums1Postion] 값을 넣고,

아니라면 nums2[nums2Postion]의 값을 넣는다.

 

그 후 1씩 감소하며 nums1과 nums2의 모든 인덱스를 비교한다.

 

이렇게 풀이하면 병합과 정렬을 하나의 반복문으로 해결할 수 있다.