[Leetcode/파이썬] 88. Merge Sorted Array

Merge Sorted Array

---

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

 

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

 

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

 

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

 

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        idx1 = m-1          # nums1의 인덱스
        idx2 = n-1          # nums2의 인덱스
        right = m + n - 1   # answer array의 총 길이

        while idx2 >= 0 :   # idx2 = -1 이 되면 그냥 그 상태로 멈추면 이미 정렬되어 있기 때문에 문제 X
            if idx1 >= 0 and nums1[idx1] > nums2[idx2] :    # idx1 = -1 이 되게 되면 idx2가 0이 될 때 까지 else문만 동작시키면 됩니다.
                nums1[right] = nums1[idx1]
                idx1 -= 1
            else :
                nums1[right] = nums2[idx2]
                idx2 -= 1
            right -= 1

이 문제는 쉽겠는데? 해서 풀어봤더니 안 풀려서 다른 분의 풀이를 참고하고 해석해보았다. 

처음에 생각했을 때는 두개를 비교해서 하나씩 채워넣으면 되는거 아니야? 라고 했는데 연속해서 nums2나 nums1이 변해야 하는 경우는 조금 어렵게 느껴졌다. 그래서 뒤에서 부터 채워볼까? 하고 들어갔더니 비교가 너무 힘들어서 어쩌지 했는데 nums1도 nums2도 뒤에서 부터 비교하면 되는 것이었고 그래서 m과 n을 줬구나 하는 생각이 들었다. 

이 풀이는 뒤에서 부터 접근하는 풀이이다. 쉽게 nums1[-1]과 nums2[-1]끼리 비교해나가는 문제라 볼 수 있다. 그러나 이부분을 pop하지 않고 포인터만 옮겨가면서 실행할 것이다. 

1. 우선 인덱싱 부터 하자. len(nums1) = m, len(nums2) = n 이기 때문에 idx1 = m - 1, idx2 = n - 1 로 둔다. 그리고 정답 리스트의 총 길이는 right = m + n - 1 로 둔다. 실제 nums1의 마지막 인덱스 이다. 
2. while idx2 >= 0 : 에 대해서 공부하자. 
   1. idx2 = -1 이 되면 그냥 그 상태로 두면 된다. 문제를 보면 각 배열들은 이미 오름차순으로 정렬되어 있는 것을 알 수 있다. nums1의  0으로 표기된 자리는 빈 자리이기 때문이다. 
   2. idx1 = -1 이 되면 남은 nums2 만큼은 while 문을 반복하면서 nums1에 옮기면 된다. 
3. 이렇게 while문 내의 if-else문을 해결하면 총 길이를 -1 해준다. 

이 과정을 마치게 되면 num1은 nums1과 nums2를 병합 정렬한 결과를 얻을 수 있다.