[Leetcode] 88. Merge Sorted Array - JS

https://leetcode.com/problems/merge-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

조건
- nums1, nums2 정수 배열 주어진다.
  - 오름차순 정렬이다.
- nums1과 nums2의 요소 갯수를 의미하는 m, n 정수가 주어진다.

결과
  -> nums1, nums2를 오름차순 정렬로 병합해라.
  단, 새로운 배열을 반환하지 말고 nums1 배열을 수정하라.

제한사항
- nums1.length == m+n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- -10^9 <= nums1[i], nums2[j] <= 10^9

 

 

2.  접근 방법

2-1. sort 정렬 방법

non-decreasing order를 오름차순으로 생각하여 오름차순 정렬된 두 배열 있다고 생각했다.

 1. nums1 배열의 마지막요소에 nums2의 첫번째 요소를 할당한다.
    - m 부터 시작해서 n 길이만큼 순회한다.
 2. sort로 정렬한다.

 

 

풀이

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

 

위 풀이의 시간 복잡도와 공간 복잡도는 다음과 같다.

- 시간 복잡도: O((m+n)log(m+n))
- 공간 복잡도: O(1)

 

 

2-2. 투 포인터 방법

시간 복잡도를 O(m+n)으로 개선한 접근법

투포인터 접근 방법

1. nums1의 포인터 i, nums2의 포인터 j, 비교한 값을 배치할 포인터 k를 선언한다.

2. nums2 포인터가 0이상이면 계속 반복한다. 
- 왜냐하면 nums1 배열은 이미 오름차순 정렬되어 있으니 nums2 요소만 비교가 끝나면 된다.

3. nums1[i] > nums2[j] 만족하면, 
- 맨 뒤에서부터 시작하는 k 포인터에 nums1[i]를 할당한다.
- i >= 0 조건을 추가한 이유는 i 포인터가 이미 모든 요소를 다 순회한 이후에는 -1이 되므로
  그 때 undefined가 할당되는 것을 막기 위함이다.

 

투포인터 접근 시 포인터 위치를 뒤에서부터 시작한 이유는 nums1, nums2 배열이 이미 오름차순 정렬되어있기 때문에

두 숫자를 비교하여 nums1 배열의 뒤에서 부터 할당하는 것이 편하기 때문이다.

 

 

풀이

var merge = function(nums1, m, nums2, n) {
    let i = m - 1;
    let j = n - 1;
    let k = m + n - 1;

    while (j >= 0) {
        if (i >=0 && nums1[i] > nums2[j]) {
            nums1[k] = nums1[i];
            i--;
        } else {
            nums1[k] = nums2[j];
            j--;
        }
        k--;
    }
}

 

위 풀이의 시간 복잡도와 공간 복잡도는 다음과 같다.
- 시간 복잡도: O(m+n)
- 공간 복잡도: O(1)