[LeetCode] 88. Merge Sorted Array

 

https://leetcode.com/problems/merge-sorted-array/?envType=study-plan&id=data-structure-i 

Merge Sorted Array - LeetCode

 

두 개의 오름차순 정렬된 list를 merge하는 문제

nums1의 길이가 m, nums2의 길이가 n

 

시간복잡도를 O(m+n)으로 만든는 것이 최적 솔루션

 

하지만 나 프로개발자 코드 생산성을 최대로 하는 O( (m+n)log(m+n) ) 코드를 먼저 만들기

 

파이썬 정답1.

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1[:]=sorted(nums1[:m]+nums2[:n])

 

이렇게 짜면 바로 코딩 테스트는 탈락

 

2개의 리스트를 탐색하면서 nums1 리스트에 insert하는 것이 진짜 원하는 답이겠지

 

파이썬 정답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.
        """

        i = m - 1
        j = n - 1
        for k in reversed(range(m+n)):
            if i < 0:
                nums1[:j+1] = nums2[:j+1]
            elif j < 0:
                break
            elif nums1[i] < nums2[j]:
                nums1[k] = nums2[j]
                j -= 1
            else:
                nums1[k] = nums1[i]
                i -= 1

일단 패스는 했는데 이거 좀 코드가 구린 느낌..?

 

브랜치가 많아서 브랜치는 줄이는 방향으로 개선하면 좋을듯?

 

파이썬 정답3.

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

            k -= 1

        if j >= 0:
            nums1[:j+1] = nums2[:j+1]

 

조기에 loop도 종료되고, loop내에서 브랜치도 4개에서 2개로 줄었음

condition check도 줄었나 했지만, 원래 if else에서 하던 i, j가 양수인지 체크하는 부분은 while loop의 condition check으로 들어가서 줄어들지 않았음.

 

 

결과적으로 속도는 매우 좋음

 

나보다 빠른 코드들은 뭔가 궁금해서 확인해봄

1번 풀이처럼 sort하는데 더 빠름....

python의 sort모듈이 c로 되어있어서 어떤 경우에는 더 빠를 수도 있다고 예상됨