[자료구조와 알고리즘] 88. Merge Sorted Array (Feat. 투 포인터 알고리즘)

문제 설명

LeetCode Top Interview 150 - 88. Merge Sorted Array

오름차순으로 정렬이 되어 있는 두 개의 숫자 배열 nums1, nums2 가 제공되고
첫번째 배열에서는 m개, 두번째 배열에서는 n개를 추출해서 오름순으로 정렬하여 첫번째 배열에 다시 저장하는 문제입니다.

풀어보기

첫번째 배열 nums1이 이미 m+n크기이고 주어진 배열은 이미 오름순으로 정렬되어 있기 때문에
순서대로 대소비교를 하여 nums1에 담아주는 방식으로 풀어보았습니다.
저는 투 포인터(Two Pointers) 알고리즘을 사용해서 각 배열에서 가르키는 위치를 다르게 사용했습니다.

그런데 두번째 배열 nums2가 빈배열인 경우에는 숫자와 undefined의 대소 비교를 하기 때문에
항상 false라는 결론이 나와서 undefined가 최종적으로 남는 예외가 발생했습니다.
그래서 저는 대소비교를 하기 전에 두번째 배열이 빈배열인지 먼저 확인하는 코드를 추가했습니다.

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    const temp = nums1.slice(0,m);
    let nums1Idx = 0;   // nums1 배열에서 사용할 인덱스(포인터)
    let nums2Idx = 0;   // nums2 배열에서 사용할 인덱스(포인터)
    for (let i=0; i<m+n; i++) {
        if (nums2[nums2Idx] === undefined || temp[nums1Idx] < nums2[nums2Idx]) {
            // nums2 배열이 빈 배열 이거나 || nums1 배열의 요소가 nums2 배열의 요소보다 작을때
            nums1[i] = temp[nums1Idx++];
        } else {
            nums1[i] = nums2[nums2Idx++];
        }
    }
};

더 좋은 코드

사실 1ms 빠르고 0.1MB 적게 사용하는 코드라서 생각보다 엄청난 차이는 아니지만!
배열의 마지막 인덱스부터 사용해서 첫번째 배열을 채워나가는 방법으로
1. 빈배열일때의 예외 상황이 발생하지 않고
2. nums1배열의 복사본을 만들 필요가 없기때문에
더 유리하다고 생각해서 가져왔습니다.

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    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--];
        } else {
            nums1[k--] = nums2[j--];
        }
    }
};

마무리

문제를 풀 때 저는 배열 인덱싱보다 대소비교에 더 초점을 두게 된 것 같습니다.
undefined와 대소비교를 한다면 무조건 false!
null과 대소비교를 한다면 음수보다는 크다고 나오지만 0과의 비교는 다양한 결론이 나옵니다..
null > 0 과 null < 0 은 false지만
null >= 0 과 null <=0 은 true입니다!