[LeetCode] 88. Merge Sorted Array, Easy

1. 문제

• 배열 nums1, nums2가 주어지고, 각각의 길이 m과 n이 주어질 때, 두 배열의 요소를 오름차순으로 정렬하여 nums1 배열에 채워라.
• 단, nums1 배열은 m+n 길이를 가지고, m만큼은 요소가 채워져있고 나머지 n은 0으로 채워져 있다. 이는 nums2의 길이와 같다.

2. 풀이

/**
 Do not return anything, modify nums1 in-place instead.
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
    let index_1 = m-1; // nums1을 가리키는 포인터
    let index_2 = n-1; // nums2를 가리키는 포인터
    
    for(let i = m + n - 1; i >= 0; i--) { // nums1 마지막부터 탐색.
        if(index_1 < 0) { // 인덱스가 넘어간 경우는 무조건 반대쪽 값을 채택.
            nums1[i] = nums2[index_2];
            index_2--;
        }
        else if(index_2 < 0) {
            nums1[i] = nums1[index_1];
            index_1--;
        }
        else {
            if(nums1[index_1] >= nums2[index_2]) { // 비교해서 큰 값을 넣고 해당 인덱스 감소
                nums1[i] = nums1[index_1];
                index_1--;
            } else {
                nums1[i] = nums2[index_2]; 
                index_2--;
            }
        }
    }
};

• n 만큼 자리수가 nums1에 존재하니까, 일단 반복은 nums1 길이 만큼 반복한다.
• 맨 뒤에서 부터 두 배열을 가리키는 포인터를 이용해 큰 값을 찾아 채워 넣는다.
• 한 쪽이 먼저 다 채워진 경우는 반대쪽 요소로 다 채운다.
• 또포인터 알고리즘.