88. Merge Sorted Array (정렬 배열 병합)

link

 

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

# 풀이 1 : 정렬 함수 사용
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.
        """
        for i, v in enumerate(nums2):
            nums1[m+i] = v
            
        nums1.sort()

# 풀이 2 : 비교 및 삽입
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.
        1) 둘 다 정렬된 배열이므로 제일 큰 값부터 비교하여 뒤에서 부터 삽입한다.
        2) j가 아직 0보다 크면  empty 값 빼면서 nums1 에 삽입
        
        [4,5,6,0,0,0]
             i     empty
             
        [1,2,3]
             j
        """
        
        i = m - 1    # nums1 마지막 값 인덱스
        j = n - 1    # nums2 마지막 값 인덱스
        empty = len(nums1) - 1  
        
        while i >= 0 and j >= 0 :
            if nums1[i] < nums2[j]:
                nums1[empty] = nums2[j]
                j -= 1
                
            else :
                nums1[empty] = nums1[i]
                i -= 1
                
            empty -= 1
        
        print(i,j,empty)
        while j >= 0 :
            nums1[empty] = nums2[j]
            empty -= 1
            j -= 1