[LeetCode/Easy] 88. Merge Sorted Array

88. Merge Sorted Array

 

통과하지 못한 이유를 종합적으로 생각해 봤을 때, 답안 예시와 같은 approach를 생각했으나 이진 탐색으로 풀어보려고 해서 더 어려웠던 것으로 보인다. 처음부터 (상대적으로) 난이도가 어려운 알고리즘으로 풀려고 하지 말고, time complexity가 어떻든 반복문으로 이해하기 쉽게 구현해 보자. 그 이후에 time complexity를 줄일 방법을 생각해 보자. 즉, 문제를 풀 때 어려운 방법보다는 쉽고 단순한 방법으로 먼저 접근하고 이후 효율화하자. 

효율화할 때 time/space complexity를 줄일 수 있는 조건문의 논리연산자를 고민해 보자. 같은 말을 두 번 체크하고 있을 수도 있다.

내 풀이 vs. 답안 풀이

---

	내 풀이	답안 풀이
in-place의 정의	값을 바꾸는 것 따라서, 다른 객체를 참조하거나 새로운 객체로 생성해도 된다고 생각함.	기존 객체를 변경하는 것이므로 내 풀이에서 말한 경우는 모두 해당 안됨.

내 답안

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.
        """
        if m == 0:
            nums1 = nums2
        elif n != 0:
            nums1 = nums1[:m] + nums2[:n]
            nums1.sort()

 

if문이랑 elif문 안에 nums1이 바뀌지 않는다. 왜지?

 

 

in-place 연산의 정의를 잘못 알고 있었다.....!!!!! "in-place"란 기존 객체를 변경하는 것을 말한다.

if문 내 코드의 경우 다른 객체를 참조하게 했고, elif문 내 코드의 경우 리스트 슬라이싱을 사용해 새로운 객체를 생성했다.

즉, 기존 객체가 아닌 다른 객체로 변경했기 때문에 바뀌지 않았던 것이다.

 

01

문제 풀면서 작성한 메모

답안 예시

Approach 1: Merge and sort

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()

• Time complexity: $O((n+m)log(n+m))$
• Space complexity: $O(n)$, but it can vary.

Approach 2: Three Pointers (Start From the Beginning)

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.
        """
        # Make a copy of the first m elements of nums1.
        nums1_copy = nums1[:m] 
        
        # Read pointers for nums1Copy and nums2 respectively.
        p1 = 0
        p2 = 0
        
        # Compare elements from nums1Copy and nums2 and write the smallest to nums1.
        for p in range(n + m):
            # We also need to ensure that p1 and p2 aren't over the boundaries
            # of their respective arrays.
            if p2 >= n or (p1 < m and nums1_copy[p1] <= nums2[p2]):
                nums1[p] = nums1_copy[p1] 
                p1 += 1
            else:
                nums1[p] = nums2[p2]
                p2 += 1

• Time complexity: $O(n+m)$
  • 더 정확하게는 $n + 2*m$인데 그 이유는 nums1_copy 만드는 과정에서 추가로 m이 더 소요된 것으로 보임
• Space complexity: $O(m)$
  • nums1_copy 만들었으므로 추가로 $m$이 더 필요
  • 기존의 nums1을 바꾼 것이므로 $n + m$은 아님

Approach 3: Three Pointers (Start From the End)

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.
        """
        
        # Set p1 and p2 to point to the end of their respective arrays.
        p1 = m - 1
        p2 = n - 1
    
        # And move p backward through the array, each time writing
        # the smallest value pointed at by p1 or p2.
        for p in range(n + m - 1, -1, -1):
            if p2 < 0:
                break
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1

• Time complexity: $O(n+m)$
• Space complexity: $O(1)$

Array 문제 풀 때는 보통 순차적으로 반복하는 것을 먼저 생각하지만, 역순으로 반복하는 알고리즘을 늘 고려하자! 문제를 훨씬 쉽게 풀 수 있을지도 모른다~~