[LeetCode] 88. Merge Sorted Array

오늘부터 1일 😃

👿 문제 88. Merge Sorted Array

1. nums1, nums2 는 오름차순 배열
2. nums1 의 길이는 m+n , nums2 의 길이는 n
3. nums1 배열에 nums2 배열을 하나로 병합하기
4. nums1배열에서 처음 m 개 요소는 병합해야 하는 요소,
   마지막 n 개 요소는 0으로 설정되어 무시하는 요소
5. ⚠️ 최종 정렬된 배열은 함수 return이 아니라 nums1 에 저장하기

😈 풀이

var merge = function(nums1, m, nums2, n) {
    if(n !== 0) nums1.splice(-n)  // 🐶
    let num1Idx = 0	// 🐱
    let num2Idx = 0
    
    for(let i=0; i<m+n; i++) { // 🐹
        if(num2Idx >= n) {	// 🐰
            break;
        }
      
        if(num1Idx >= m) {	// 🦊
            nums1.push(nums2[num2Idx])
            num2Idx = num2Idx + 1
            continue;
        }

        if(nums1[num1Idx] >= nums2[num2Idx]) {	// 🐻
            nums1.push(nums2[num2Idx])
            num2Idx = num2Idx+1
        } else {
            num1Idx = num1Idx+1	// 🐼
        }   
    }

    nums1.sort((a, b) => a-b)	// 🐥
};

1. n이 0이 아닐 때, 무시할 마지막 n개 요소를 nums1에서 삭제한다. (🐶)
2. nums1, nums2 초기 인덱스를 각각 0으로 설정한다. (🐱)
   ➡️ 오름차순 배열이므로 인덱스 0번부터 비교 시작!
3. m+n(nums1의 길이)만큼 for문을 돌린다. (🐹)
4. 예외처리 먼저 하기! (🐰)
   ➡️ nums2의 인덱스가 n(nums2의 길이)보다 커지면 끝!
5. nums1의 인덱스가 m보다 크면(nums1은 비교할 대상이 더 이상 없다) nums2의 나머지를 돌면서 nums1에 push한다. (🦊)
6. 만약 nums1의 값이 nums2보다 크거나 같으면 nums1에 push, nums2의 인덱스는 +1 (🐻)
7. nums1의 값이 nums2의 값보다 작으면 nums1의 인덱스 +1 (🐼)
8. 마지막에 오름차순 정렬을 해준다. (🐥)

nums1, nums2의 인덱스를 각각 지정해놓고 조건마다 비교해가며 탐색하는 Two Pointers 알고리즘
시간 복잡도 : O((m+n)log(m+n))
공간 복잡도 : O(1)

마지막에 sort를 한번 더 해줘서 시간 복잡도가 O(nlogn)이 되었다 🥲 통과는 했지만 시간 복잡도를 줄이는 방식으로 다시 풀고 추가해서 올리기!! 그리고 함수 return이 아닌지 잘 읽기!!

✅ 1일1알