문제 푼 날짜 : 2021-11-29

문제

문제 링크 : https://leetcode.com/problems/merge-sorted-array/

접근 및 풀이

처음 보자마자 임의의 vector를 두고 mergesort를 하듯이 구현하려고 하였으나, 입력으로 주어지는 nums1 vector에 결과를 저장해야했다. 그러면 C++의 sort 함수를 이용해야 하고, 다시 nums1 vector에 저장된 값들을 옮겨야 하는 과정이 필요했다. 너무 코드가 지저분해질 것 같아서 그렇게 풀기 싫었다.
in-place sort를 구현하기 위해 각 vector들(nums1, nums2)의 맨 앞자리부터 비교하는 것이 아니라, 뒷자리부터 비교하면서 큰 값을 먼저 nums1에 정렬해주었다.

코드

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int mIdx = m - 1, nIdx = n - 1, totIdx = m + n - 1;
        
        while (mIdx >= 0 && nIdx >= 0) {
            if (nums1[mIdx] >= nums2[nIdx]) {
                nums1[totIdx--] = nums1[mIdx--];
            } else {
                nums1[totIdx--] = nums2[nIdx--];
            }
        }
        while (nIdx >= 0) {
            nums1[totIdx--] = nums2[nIdx--];
        }
    }
};

결과

피드백

접근 방법을 다양하게 생각할 수 있도록 문제를 풀고나서 다양한 풀이를 섭렵하도록 하자.