Leetcode - 88. Merge Sorted Array

오늘 Pramp mock 인터뷰 해보면서 알게된 사실. (https://velog.io/@soopsaram/Pramp-Drone-Flight-Planner)
나는 인터뷰같은 압박의 상황에서 코딩시 array indexing에 대해 더욱 햇갈려한다는 사실을 깨달았다. array의 index를 조작해야하는 문제들 많이 풀어보기!
Pramp array 참고 자료

문제

주어진 정렬된 두개의 배열을 합치기(정렬된상태로). 주의할점은 nums1에 합쳐진 값들을 저장해야한다는것. 따라서 nums1[]배열의 크기는 m+n이다. nums1 크기 m, nums2크기 n

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

https://leetcode.com/problems/merge-sorted-array/

해결 O(m) / O(1)

우선 nums1[]을 통째로 우측으로 이동시키고, nums1[] 과 nums2[]의 값을 하나씩 비교하면서 nums1[0]부터 저장. 이렇게 하면 리니어한 시간복잡도에 결과를 도출할 수 있음. 아래 코드 결과는 faster than 100.00%

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
    int st_m = n;
    int st_n = 0;
    int arrcnt = 0;
    
    for (int i = nums1Size - n - 1; i >= 0; i--)
        nums1[i + n] = nums1[i];

    while (arrcnt < nums1Size) {
        if (st_m >= nums1Size) {
            nums1[arrcnt++] = nums2[st_n++];
            continue;
        }
        if (st_n >= nums2Size) {
            nums1[arrcnt++] = nums1[st_m++];
            continue;
        }
        if (nums1[st_m] > nums2[st_n])
            nums1[arrcnt++] = nums2[st_n++];
        else
            nums1[arrcnt++] = nums1[st_m++];
    }
}