[LeetCode] 88. Merge Sorted Array 파이썬(Python) 풀이

문제 링크

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

Merge Sorted Array - LeetCode

 

merge sort 에서 가장 핵심이 되는 merge 함수의 in-place 구현을 하는 문제입니다.

in-place 란, 주어진 메모리와 O(1) 의 추가 메모리만 사용하라는 것입니다.

O(1) 의 추가 메모리란, 추가로 사용하는 메모리의 크기가 입력 값의 크기와 무관하다는 것을 의미합니다.

 

풀이의 핵심은 nums1 의 뒷 부분은 비어 있으니, 뒤부터 채우면 필요한 값이 덮어써지는 경우가 없기 때문에 뒤 부터 채우는 것입니다.

 

소스 코드는 다음과 같습니다.

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 k >= 0:
            if i < 0:
                nums1[k] = nums2[j]
                j -= 1
            elif j < 0:
                nums1[k] = nums1[i]
                i -= 1
            elif nums1[i] < nums2[j]:
                nums1[k] = nums2[j]
                j -= 1
            else:
                nums1[k] = nums1[i]
                i -= 1
            k -= 1

 

중복 코드가 있는게 썩 마음에 들지 않기는 합니다만,, 어떻게 중복을 없앨지 애매해서 그냥 두었습니다.

제출하고 나니 k 에 대하여 while 문 대신 for 문으로 변경하면 코드가 좀 더 간결해질 것 같네요.

 

유튜브에서 라이브로 풀이를 했었는데 반응이 썩 좋지 않았어서, 풀이 영상은 어떻게 할지 아직 고민 중입니다.

그리고 라이브로 풀었을 때에는 j < 0 인 경우에 어차피 nums1 에 값이 다 들어간 것이기 때문에 그냥 break 하도록 풀었었네요. 당연하지만 중간에 break 하는게 더 빠르겠지요?

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)