Leetcode 88. Merge Sorted Array (C++)

오랜만에 문제를 풀어봤다.

머리가 잘 안돌어가더라

import할 헤더도 기억이 잘 안나고.. 막 멤버 함수도 기억이 안나고 그래서 릿코드를 가져왔다.

 

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

 

정답 코드는 아래와 같다.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {

        // for two pointer for two arrays        
        int i = m - 1, j = n - 1, k = m + n - 1;

        // evade null pointer
        while(i >= 0 && j >= 0) {
            // non-decreasing sorted array
            if(nums1[i] >= nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }

            k--;
        } 

        // step 3: insert the remaining elements from nums2
        while(j >= 0){
            nums1[k--] = nums2[j--]; 
        }
    }
};

 

내 생각 과정은 아래처럼 생각했다.

 

1. output이 없고 nums1에 채워서 내는거네

2. nums1 + nums2 를 합쳐야하네

3. 입출력 제한을 볼까?

4. integer 범위 내, 200정도의 입력이네 어떻게 하든 풀기만 하면 시간초과는 안나는 문제네

5.  이런 문제는 조금 더 멀리서 봐야 잘 보인다.

6. 이미 정렬되어 있으니 배열의 앞부분부터 각 원소를 하나씩 비교해서 작은 것부터 새로운 배열에 넣는 것은 어떨까?

7. nums1에 채워야 하는거라 별로네..?

8. 엇.. 그럼 맨 뒤에서부터 큰 것부터 넣는 것은 어떨까?

9. 정답

 

모두가 알고리즘을 위처럼 풀지는 않겠지만 이 과정을 풀어서 써보면 그렇다.