[Easy] 정렬된 배열 병합 - 88. Merge Sorted Array

정수 배열 nums1과 nums2가 오름차순으로 정렬되어 주어지며, 각각의 요소 개수를 나타내는 정수 m과 n도 주어집니다.

nums1과 nums2를 병합하여 오름차순으로 정렬된 단일 배열로 만들어야 합니다.

 

최종 정렬된 배열은 함수에 의해 반환되지 않고 nums1 배열 내에 저장되어야 합니다. 이를 위해 nums1의 길이는 m + n이며, 처음 m개의 요소는 병합해야 하는 요소를 나타내고, 마지막 n개의 요소는 0으로 설정되어 무시되어야 합니다. nums2의 길이는 n입니다.

예제 1:

입력: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
출력: [1,2,2,3,5,6]
설명: 병합하려는 배열은 [1,2,3]과 [2,5,6]입니다.
병합 결과는 [1,2,2,3,5,6]이며, 밑줄 친 요소는 nums1에서 왔습니다.

예제 2:

입력: nums1 = [1], m = 1, nums2 = [], n = 0
출력: [1]
설명: 병합하려는 배열은 [1]과 []입니다.
병합 결과는 [1]입니다.

예제 3:

입력: nums1 = [0], m = 0, nums2 = [1], n = 1
출력: [1]
설명: 병합하려는 배열은 []과 [1]입니다.
병합 결과는 [1]입니다. m = 0이기 때문에 nums1에는 요소가 없습니다. 0은 병합 결과가 nums1에 맞도록 보장하기 위해 존재합니다.

제약 사항:

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

 

 

중요한 키 포인트는 두 배열이 이미 오름차순으로 정렬되어 있다는 것이다.

즉 뒤에서부터 읽어가며 비교하면 두 배열에서 가장 큰 수를 알 수가 있다.

이 방법을 이용하면 O(m+n)으로 정답을 구할 수가 있다.

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.
        """
        i = m - 1
        j = n - 1
        k = m + n - 1
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                k -= 1
                i -= 1
            else:
                nums1[k] = nums2[j]
                k -= 1
                j -= 1