[알고리즘/Python] LeetCode 88.Merge Sorted Array

문제 

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

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Example 1:
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.

Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The arrays we are merging are [1] and []. The result of the merge is [1].

Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Explanation: The arrays we are merging are [] and [1]. The result of the merge is [1]. Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
 
Constraints:
· nums1.length == m + n
· nums2.length == n
· 0 <= m, n <= 200
· 1 <= m + n <= 200
· -10^9 <= nums1[i], nums2[j] <= 10^9

---

 이 문제는 두개의 오름차순으로 정렬된 배열을 합쳐서 하나의 오름차순 배열로 만드는 것입니다. 이때 중요한 것은 새로운 배열을 만들어서 반환하는 것이 아니라 기존의 배열 nums1에 정렬된 배열을 저장하는 것입니다.

💡 접근 방법 : 투포인터

각 배열의 비교할 원소를 가리키기 위해서 두개의 포인터를 사용하는 방법입니다. 각 배열에서 포인터가 가리키는 원소의 값을 비교하여 작은 쪽의 원소를 꺼내 새로운 배열에 저장하는 작업을 반복해 정렬된 배열을 만듭니다. 

 

1. 병합된 배열을 저장할 새로운 배열(result)과, 각 배열의 첫번째 원소를 가리키는 두개의 포인터(p1, p2)를 초기화합니다.

2. 각 포인터가 가리키는 원소의 값을 비교하여 더 작은 쪽의 원소를 result 배열의 끝에 추가하고, 추가된 원소를 가리키는 포인터를 오른쪽으로 옮깁니다.

• 이때 다른쪽 배열을 가리키는 포인터는 이동하지 않습니다.
• 두 원소의 값이 같다면 nums1 배열을 선택합니다.

3. 두개의 포인터 중 하나가 배열의 끝에 도달할때까지 2.를 반복합니다.

• 배열의 끝은 배열의 마지막 인덱스 + 1(혹은 배열의 길이)을 말합니다. 즉, 더 이상 배열의 원소를 가리키지 않는 상태입니다.

4. 반복문이 끝나고 난 후, 배열에 남은 원소가 있다면 그 원소들을 result배열의 끝에 추가합니다. 배열에 남은 모든 원소는 result 배열의 가장 큰 원소보다 항상 크고, 오름차순으로 정렬된 상태이기 때문에 result배열 끝에 그대로 추가해주면 됩니다.

5. result배열의 모든 원소를 nums1배열에 옮겨서 저장합니다.

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        result = []
        p1 = p2 = 0
        while p1 < m and p2 < n:
            if nums1[p1] <= nums2[p2]:
                result.append(nums1[p1])
                p1 += 1
            else:
                result.append(nums2[p2])
                p2 += 1

        while p1 < m:
            result.append(nums1[p1])
            p1 += 1

        while p2 < n:
            result.append(nums2[p2])
            p2 += 1

        for i in range(n + m):
            nums1[i] = result[i]

 

🚨 주의할 점:  단순히 배열이 참조하는 주소를 바꾸면 안됨

 위 코드에서 마지막 for문( result배열의 모든 원소를 nums1으로 복사)을 단순히 배열이 참조하는 주소를 바꾸도록 다음과 같이 코드를 작성하면

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        result = []
        p1 = p2 = 0
        while p1 < m and p2 < n:
            if nums1[p1] <= nums2[p2]:
                result.append(nums1[p1])
                p1 += 1
            else:
                result.append(nums2[p2])
                p2 += 1

        while p1 < m:
            result.append(nums1[p1])
            p1 += 1

        while p2 < n:
            result.append(nums2[p2])
            p2 += 1

        nums1 = result

 다음과 같이 실패하게 됩니다.

 

 LeetCode가 배열에 저장된 원소를 검사할때 그 배열이 현재 참조하고 있는 주소가 아니라 기존 배열의 주소를 기억해두었다가, 그 주소에 저장된 값을 검사하기 때문이라고 추측하였습니다. 

 

LeetCode가 제출된 답변을 검사하는 쪽의 코드는 다음과 비슷할 것입니다.

import MergeSortedArray
import ctypes


class Algorithm:
    def check_submission(self, nums1, m, nums2, n, expected):
        memory_address = id(nums1)

        s = MergeSortedArray.Solution()
        s.merge(nums1, m, nums2, n)

        actual = ctypes.cast(memory_address, ctypes.py_object).value

        print(actual)
        return expected == actual

python에서 메모리 주소로 실제 값을 가져오는 방법에 대해 궁금하시다면 다음 링크를 참고해주세요.

https://www.geeksforgeeks.org/how-to-get-value-from-address-in-python/

✔ 시간 복잡도 및 공간 복잡도

시간 복잡도: O(N+M)

• nums1 배열의 길이를 N, nums2배열의 길이를 M이라고 할때,
• nums1, nums2의 원소를 비교해서 오름차순으로 result 배열에 저장하기 위해서는, 배열의 원소를 참조하는데 O(1), 원소를 result 배열의 끝에 append 하는데 O(1) 시간이 소요됩니다. 이 연산을 배열의 모든 원소에 대해서 수행하므로 총 O((N+M)*1) 시간이 소요됩니다.
• result의 원소를 nums1배열에 옮겨 저장하기 위해서는 각 원소를 인덱스로 참조하는 연산을 N + M개의 원소에 대해서 수행하므로  O((N+M) * 1) 시간이 소요됩니다.
• 따라서 Big-O 표기법에 의한 시간 복잡도는 O(N+M)이 됩니다.

공간 복잡도: O(N+M)

• nums1 배열의 길이를 N, nums2배열의 길이를 M이라고 할때,
• nums1배열을 저장하는데 O(N), nums2 배열을 저장하는데 O(M), result 배열을 저장하는데 O(N+M) 공간이 필요합니다.
• 따라서, 공간 복잡도는 O(N+M)이 됩니다.

---

⚒️ 개선: 큰 원소부터 저장하기

큰 원소부터 정렬해가면 시간복잡도와 공간복잡도 모두 개선할 수 있습니다.

 

위에서는 배열의 가장 앞에서부터 비교해서 작은 원소부터 저장나가기 위해 새로운 배열이 필요했습니다. nums1 배열에 저장하면 아직 비교되지 않은 원소를 덮어쓰게 되기 때문입니다.

 

하지만 생각을 배열의 가장 뒤에서부터 비교해서 큰 원소부터 저장해 나간다면 nums1 배열 공간을 활용할 수 있게 되고 추가적인 공간이 필요하지 않습니다. 또,  정렬이 모두 끝난 후 새로운 배열에 저장된 값을 nums1 배열에 옮길 필요도 없게 되어 연산 횟수를 줄일 수 있습니다.

 

1. 포인터 i, j는 각 배열의 가장 큰 원소를 가리키도록 초기화합니다. 또, 정렬된 원소를 저장할 인덱스를 가리키는 포인터 k는 nums1배열의 마지막 인덱스를 가리키도록 초기화합니다.

2. 포인터 i, j가 가리키는 값을 비교하여 큰 원소를 nums1[k]에 저장합니다. 포인터를 조정합니다. 만약, nums1의 모든 원소를 비교한 후에 nums2에 남아있는 원소가 있다면 그 순서대로 nums1 배열에 옮깁니다. 비교한 원소의 값이 같을 경우 nums2의 값을 저장합니다.

3. j가 0보다 작아질때까지 즉, nums2의 모든 원소를 정렬된 순서로 nums1에 저장할때까지 위의 2.를 반복합니다.

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        i = m - 1
        j = n - 1
        k = m + n - 1
        
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

다음 링크의 코드를 참고하였습니다.

https://leetcode.com/problems/merge-sorted-array/solutions/3436053/beats-100-best-c-java-python-and-javascript-solution-two-pointer-stl/?envType=study-plan-v2&envId=top-interview-150

 

위와 같은 방법이 가능한 이유는 nums1의 마지막 N개의 원소는 정렬된 원소가 저장될 공간을 나타내는 dummy 원소들이기 때문에 덮어써도 괜찮습니다. 또 nums2의 모든 원소를 정렬했다면 nums1에서 아직 비교되지 않은 원소들도 오름차순으로 정렬되어있다는 의미입니다.

 

이 방법도 최악의 경우 모든 원소를 한번씩 방문해야하므로 빅오 시간복잡도는 O(N+M)으로 위의 방법과 동일합니다. 다만 result배열의 원소를 nums1으로 복사하는 연산을 생략할 수 있어 실행 시간이 단축됩니다.

---

⚒️ 응용: 병합 정렬 알고리즘

위의 정렬을 마친 배열의 병합 응용하여 분할 정복법에 따라 정렬하는 병합 정렬(Merge Sort)을 수행할 수 있습니다. 

 

병합정렬이란 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘 입니다.

 

1. 배열을 앞부분과 뒷부분으로 나눕니다. 

2. 나눈 두 배열을 각각 병합 정렬로 정렬합니다.

3. 정렬된 각각의 배열을 병합하여 배열 정렬을 완료합니다.

---

🔖 정리

⊙ 정렬된 배열을 병합할때는 투 포인터를 사용해서 각 배열의 값을 비교하여 작은 값 부터 혹은 큰 값부터 정렬해나갈 수 있습니다. 

⊙ 이때 각 원소를 한번씩만 참조하게 되므로 시간복잡도는 O(N + M)이 됩니다. 

⊙ 큰 값들을 내림차순으로 정렬하며 nums1 배열의 뒤에서부터 저장해간다면 추가 공간이 필요하지 않게 되어 공간복잡도가 O(1)이 됩니다.

⊙ 정렬된 배열을 병합하는 알고리즘을 응용하여 병합정렬을 수행할 수 있습니다. 

⊙  LeetCode에서 함수가 배열을 반환하는 것이 아닌 지정된 배열에 결과를 저장해야하는 경우 변수가 참조하는 주소를 변경하는 것이 아니라, 지정된 주소의 값을 직접 변경하여야합니다.