[Leetcode] 88. Merged sorted array (python)

#1.  문제

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

 

Merge Sorted Array - LeetCode

 

m+n 길이를 가진 정수 리스트 nums1과 n의 길이인 정수 리스트 nums2를 합쳐서 내림차순으로 정렬된 nums1 도출

nums1의 실질적인 요소는 처음 m개이며 이후 nums2의 길이 만큼 0으로 채워진다.

 

# input
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

# output
Output: [1,2,2,3,5,6]

 

# 참고로 num1 내부적인 요소 변동이 있어야 하므로 함수 내부에 return 값은 존재하지 않는 것이 문제 요구사항

---

 

#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.
        """

        nums1[m:] = nums2
        nums1.sort()

 

nums1의 실질적인 요소는 앞에서부터 m개이기 때문에 m개 이후의 요소를 nums2로 치환한다.

리스트를 반환하지 않고, 기존 리스트 내부 요소를 변경해야 하기 때문에 list1 = list2 등으로 객체 자체를 치환할 수 없다.

루프와 포인터로 요소간 대소비교 후 적재를 하는 방식도 더러 있지만, 위 풀이처럼 슬라이싱 방식도 기존 리스트의
변화가 in-place 형태로 이루어지기 때문에 추가적인 메모리 낭비도 없으며 시간복잡도 역시 O(N)으로 처리할 수 있다.
무엇보다 코드 자체가 매우 깔끔하다.