[LeetCode] Merge Sorted Array

목차

문제

• nums1의 0인 부분에 nums2를 넣고 정렬된 nums1을 만드는 문제입니다.
• 예시

  • Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
    Output: [1,2,2,3,5,6]

• 제약조건
  • nums1.length == m + n
  • nums2.length == n
  • 0 <= m, n <= 200
  • 1 <= m + n <= 200
  • -109 <= nums1[i], nums2[j] <= 109

문제 풀이

풀이 1 : Merge and sort

• 풀이
  • 단순하게 그냥 nums2값을 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.
            """
            # Write the elements of num2 into the end of nums1.
            for i in range(n):
                nums1[i + m] = nums2[i]
            
            # Sort nums1 list in-place.
            nums1.sort()

• 시간복잡도
  • nums2를 nums1에 단순히 삽입하게 되면 정렬을 다시 해주어야합니다.
  • n+m 길이의 리스트를 정렬해야 하기 때문에 총 O((n+m)log(n+m))이 소요될 것입니다.

풀이 2 : Three Pointers (Start From the Beginning)

• 풀이
  • 정렬되어 있는 nums1과 nums2를 앞에서부터 값을 비교해서 값을 채우는 방식입니다. 
  • nums1 의 복사본을 만들어 둔 뒤, nums1의 인덱스 p1과 nums2의 인덱스 p2를 생성해서 for p in range(n+m)에 대해서 p1과 p2의 값을 비교해서 더 작은 값부터 차근차근 넣어줍니다.
• 코드

  • 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.
            """
            p1 = 0
            p2 = 0
    
            nums1_copy = nums1[:m]
    
            for p in range(m+n):
                if p2>=n:
                    nums1[p]=nums1_copy[p1]
                    p1+=1
                elif p1>=m:
                    nums1[p]=nums2[p2]
                    p2+=1
                else:
                    if nums1_copy[p1]<=nums2[p2]:
                        nums1[p]=nums1_copy[p1]
                        p1+=1
                    else:
                        nums1[p]=nums2[p2]
                        p2+=1

• 시간복잡도
  • O(n+m)만에 해결이 가능합니다. 바로바로 비교하면서 데이터를 쌓기 때문에 정렬을 하지 않아도 됩니다.
• 공간복잡도
  • nums1의 copy를 만들어야 하기때문에 O(m)의 공간복잡도를 가집니다.

풀이 3 : Three Pointers (Start From the End)

• 풀이
  • 정렬되어져 있는 nums1과 nums2를 뒤에서부터 값을 비교해서 값을 채우는 방식입니다. 
  • nums1의 복사본을 만들 필요가 없어 공간복잡도를 O(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.
            """
            p1 = m-1
            p2 = n-1
    
            for p in reversed(range(m+n)):
                if p2<0:
                    nums1[p]=nums1[p1]
                    p1-=1
                elif p1<0:
                    nums1[p]=nums2[p2]
                    p2-=1
                else:
                    if nums1[p1]>=nums2[p2]:
                        nums1[p]=nums1[p1]
                        p1-=1
                    else:
                        nums1[p]=nums2[p2]
                        p2-=1

• 시간복잡도
  • O(n+m)만에 해결이 가능합니다. 바로바로 비교하면서 데이터를 쌓기 때문에 정렬을 하지 않아도 됩니다.
• 공간복잡도
  • 풀이 2처럼 nums1의 copy를 만들필요가 없어 O(1)의 공간복잡도를 가집니다.

알게 된 내용

• 정렬된 두개의 배열이 존재할때는 투 포인터를 이용하여 값을 넣어주면 따로 정렬할 필요가 없어져 효율적입니다.
  • 투포인터 : O(n+m) , 정렬 : O((n+m)log(n+m))

출처

• https://leetcode.com/explore/learn/card/fun-with-arrays/525/inserting-items-into-an-array/3253/