LeetCode [88]: Merge Sorted Array

📌 LeetCode [88]: Merge Sorted Array

🔗 문제 링크

---

문제 설명 📄

두 개의 정렬된 배열 nums1과 nums2가 주어졌습니다.
nums1의 크기는 m + n이며, 처음 m개의 요소는 유효하고 나머지는 0으로 비워져 있습니다.
nums2는 크기가 n인 정렬된 배열입니다.
nums1과 nums2를 병합하여 정렬된 하나의 배열로 만들어야 하며, 제자리에서(in-place) 수정해야 합니다.

---

문제 접근 방식 📋

1. 두 포인터를 활용:
   • 배열 nums1의 끝에서부터 값을 채워 넣습니다.
   • nums1의 유효한 요소를 가리키는 포인터 left와 nums2의 요소를 가리키는 포인터 index를 사용합니다.
   • 가장 큰 값을 뒤에서부터 채워넣으며 nums1의 공간을 채웁니다.
2. 반복 조건:
   • index >= 0인 동안 두 배열을 비교하며 병합합니다.
   • nums1[left] > nums2[index]인 경우, nums1의 값을 사용하고, 그렇지 않으면 nums2의 값을 사용합니다.
3. 병합 완료:
   • 두 배열 중 하나가 소진되면 병합이 완료됩니다.

---

Solution 💻

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.
        """
        right = len(nums1) - 1  # nums1의 끝에서부터 채워넣음
        left = m - 1           # nums1의 유효 요소를 가리키는 포인터
        index = n - 1          # nums2의 요소를 가리키는 포인터

        while index >= 0:  # nums2의 요소가 남아있는 동안 반복
            if left >= 0 and nums1[left] > nums2[index]:
                nums1[right] = nums1[left]  # nums1의 요소를 뒤로 이동
                left -= 1
            else:
                nums1[right] = nums2[index]  # nums2의 요소를 채워넣음
                index -= 1
            right -= 1  # 다음 위치로 이동

---

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(m + n)
  • 두 배열의 길이를 한 번씩 순회하므로.
• 공간 복잡도: O(1)
  • 추가 메모리 없이 기존 배열 nums1을 제자리에서 수정.

---