[코딩/LeetCode150-(1)] Merge Sorted Array (88)

 

 

 

 

 

본 글은 LeetCode Top Interview 150에 정리된 문제를 요약하고 이에 대한 개인적인 풀이를 포함하고있습니다.
본 포스팅 시리즈는 150 list의 순서를 따라서 게재됩니다. 풀이 언어는 python을 사용합니다.

 

 

 

난이도: EASY

키워드: Array, Two-Pointers

 

 

문제

 

문제 원문: https://leetcode.com/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150

 

감소하지 않는 형태로 정렬된 두 개의 integer array nums1 이랑 nums2의 각각의 길이 (정수가 들어있는 배열부분의 길이)를 나타내는 두 개의 정수 m과 n이 주어졌다. 두 개의 array를 감소하지 않는 순으로 (non-decreasing order) 정렬해라.

단, 최종 결과물은 새로운 array를 반환하지 않고 nums1 배열을 수정해야한다. 이를 위해서 애초에 nums1 의 전체 길이는 m+n으로 주어진다.

 

예제 입력 

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

 

 

풀이

 

1) 생각할 수 있는 가장 쉬운 방법 (Runtime Beats 73.85 %,  Memory Beats 55.55 %)

 

• nums1 배열에 마저 채워놓고 정렬하기
• 너무 trivial한 방법이다.
• 하지만 의외로 runtime이 빠른 편 (내 코드보다 잘돼있는 python sort algorith... 🥹)

참고로 python의 sort()는 TimSort를 사용합니다. 최악 시간 복잡도 $O(n \log n)$, 평균 시간 복잡도 $O(n \log n)$, 공간 복잡도 $O(n)$

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.
        """
        for i in range(n):
            nums1[m+i] = nums2[i]
        nums1.sort()

 

2) 추가 메모리 사용하기

• 1번과 더불어 이 방법은 너무 trivial 하니까 패스, 메모리 사용량에서 이득이 없음

 

 

3) 정렬되어있는 정보 활용하기 (Runtime Beats 49.85 %,  Memory Beats 83.85 %)

 

• 참고로 앞에서부터 inplace로 대체하면 유지해야하는 정보가 많아짐
  (in-place되는 정보를 뒷 부분에 저장해놓고 비교할때마다 복잡한 조건이 필요함)
• 이를 해결하기 위해서는 역으로 뒤에서부터 채우면 된다.
• 이 아이디어를 사용하면 간단하게 세 개의 pointer로 merge 가능
  일반적으로 array 문제에서 많이 사용되는 Two pointers 기법을 응용해서 current pointer를 함께 사용

 

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

        curr, left, right = m+n-1, m-1, n-1
        while left >= 0 and right >= 0:

            if nums1[left] > nums2[right]:
                nums1[curr] = nums1[left]
                left -= 1
            else:
                nums1[curr] = nums2[right]
                right -= 1
            curr -= 1
        # only if right elements are remain
        if right >= 0:
            while right >= 0:
                nums1[curr] = nums2[right]
                right -= 1
                curr -= 1

 

참고로, 이 코드에서 nums1은 이미 left 이하의 앞쪽 부분이 sorting되어있기 때문에 left index가 >=0인 경우는 별도로 merge하는 과정을 거칠 필요가 없다. 이 아이디어는 merge sort 알고리즘의 아이디어를 그대로 활용했다.

 

 

Takeaway

 

• in-place로 merge할 때, 앞쪽부터 merge를 하게되면 num1에 이미 있는 값들에 대한 처리가 복잡해지게된다. 이를 뒤집어서 큰 수부터 비교해서 뒤쪽에서부터 merge를 해주게 되면 훨씬 간단하게 문제를 해결할 수 있다.
• 내가 붙인 키워드: Two pointers, Merge Sort

 

📚 LeetCode 75 / Code Signal 풀이 보러가기