88. Merge Sorted Array

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

 

 

문제) 

다음 두 개의 정수 배열 nums1과 nums2가 주어집니다. 두 배열은 오름차순으로 정렬되어 있습니다. 그리고 두 정수 m과 n이 주어지는데, m은 nums1 배열에서 실제로 사용되는 요소의 개수이고, n은 nums2 배열의 요소 개수입니다.

이제 nums1과 nums2를 병합하여 하나의 오름차순 정렬 배열로 만들어야 합니다.

최종적으로 정렬된 배열은 반환되지 않고, nums1 배열에 저장되어야 합니다. 이를 위해 nums1은 m + n 길이를 가지며, nums1의 첫 m개의 요소는 병합할 값들이 들어있고, 마지막 n개의 요소는 0으로 채워져 있습니다. nums2 배열의 길이는 n입니다.

 

 

 

두 배열이 이미 정렬되어있으므로 병합정렬의 병합 부분만 활용하면 된다.

이미 정렬되어있는 nums1의 뒷부분을 채워나가야 하므로  nums1와 nums2의 끝 값을 비교해서 더 큰 값을 nums1 맨 끝에 넣어준다.

비교가 끝나면 각 인덱스를 -1해서 비교한다.

 

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # 비교할 nums1의 인덱스
        i = m - 1
        # 비교할 nums2의 인덱스
        j = n - 1
        
        # 비교해서 더 큰 값을 넣을 nums1의 인덱스
        k = m + n - 1

        while i >= 0 and j >= 0:
        	# 더 큰 쪽을 nums1 끝에 넣는다.
            if nums1[i] > nums2[j] :
                nums1[k] = nums1[i]
                i -= 1
            else :
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        
        # 남아있는 nums2 배열을 그대로 nums1 뒤에서부터 넣는다.
        while j >= 0 :
            nums1[k] = nums2[j]
            j -= 1
            k -= 1