Leetcode - Merge Sorted Array

15 Oct 2024 in Algorithm

알고리즘 공부

Daily Leetcode

• ⛳️ Naive Approach.
• ✔︎ Best Approach

리트코드를 풀어보려 한다. 라이브 코테 대비용으로 말이다. 일단 목표는 3달 안에 Top 150 문제를 푸는 것이다. 문제 풀어보자.

문제 링크

⛳️ Naive Approach.

시간복잡도와 공간복잡도를 고려 안하고 가장 단순한 방법으로 먼저 풀어보자.

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

        # Naive
        ptr = m

        for num in nums2:
            nums1[ptr] = num
            ptr += 1

        nums1.sort()

        # TC: O((m+n)log(m+n))
        # SC: O(1)

일단 nums1 배열에 nums2 원소들을 모두 옮겨주고 sort() 함수를 통해 정렬을 진행하는 것이다.

이렇게 했을 때 Time Complexity : O((m+n)log(m+n)) 이며 Space Complexity 는 O(1) 이다.

이 코드의 TC를 더 줄이는 방법이 있을까?

✔︎ Best Approach

힌트로 주어진 점들

• 데이터는 오름차순으로 이미 정렬되어 있다.
  • 추가적인 정렬이 필요 없다.
• nums1의 경우 빈 데이터들은 0으로 다 채워져 있다.

그렇다면 두 개의 포인터를 이용해서 nums[idx] = element 연산 만을 통해 TC를 줄일 수 있지 않을까?

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

        # nums2 is empty
        if n == 0:
            return

        # Best Aprroach
        # use 2 pointer

        ptr1, ptr2 = m-1, n-1
        end = m+n-1

        while ptr2>=0:
            if ptr1>=0 and nums1[ptr1] > nums2[ptr2]:
                nums1[end] = nums1[ptr1]
                ptr1 -= 1
            else:
                nums1[end] = nums2[ptr2]
                ptr2 -= 1
            end -= 1

보다시피 끝에서부터 큰 값을 넣어주고 잇다. 뒤에서부터 비교하면서 제일 큰 값을 end 인덱스에 넣어주고 있는 것이다. 이렇게 되면 큰 값부터 뒤에서 정렬이 되면서 순회는 한번만 하면 되므로 Time complexity : O(m+n) 을 만족할 수 있다.

간단한 문제이나 참신하다. 항상 고민하자.