[코딩인터뷰] Leetcode - Array/String - 88. Merge Sorted Array

 

Merge Sorted Array

---

문제 - 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.

---

알아야 할 개념 공부하기 📘

 

"88. Merge Sorted Array" 문제를 해결하기 위해서는 다음과 같은 중요한 개념과 기술들을 이해해야 합니다

 

1. 투 포인터 기법 (Two-Pointer Technique):
   • 이 기법은 보통 두 배열을 순회하기 위해 인덱스(포인터)를 사용합니다. 두 배열이 모두 정렬되어 있으므로, 각 포인터가 현재 가리키고 있는 원소를 비교하고 그에 따라 포인터를 이동시킬 수 있습니다.
2. 제자리 배열 조작 (In-Place Array Manipulation):
   • nums1 배열을 제자리에서 수정해야 합니다. 이는 아직 비교되지 않은 nums1의 원소를 덮어쓰지 않도록 주의해야 함을 의미합니다.
3. 뒤에서부터 작업하기 (Working Backwards):
   • nums1이 최종 병합된 배열을 담아야 하고 끝에 충분한 공간이 있기 때문에, nums1의 끝부터 시작하여 가장 큰 원소부터 채워나갈 수 있습니다. 이렇게 하면 공간을 만들기 위해 원소들을 이동시킬 필요가 없습니다.
4. 비감소 순서 이해하기 (Understanding Non-Decreasing Order):
   • 비감소 순서란 같은 원소가 있을 수 있지만, 이전 원소보다 작지 않은 순서로 정렬된 시퀀스를 의미합니다 (즉, 오름차순 또는 같은 순서입니다).
5. 경계 조건 처리하기 (Edge Cases):
   • 한 배열이 다른 배열보다 먼저 소진되는 경우를 처리할 수 있어야 합니다. 이는 m이나 n이 0일 때 발생하거나 한 배열의 모든 원소가 다른 배열보다 먼저 배치될 때 발생할 수 있습니다.
6. 시간 복잡도 (Time Complexity):
   • 후속 질문은 O(m + n) 시간 복잡도를 가진 최적의 해결책을 암시합니다. 즉, 해결책은 각 배열을 최대 한 번씩만 순회해야 합니다.
7. 프로그래밍 언어 문법 (Programming Language Syntax):
   • 이 문제를 해결하기 위해 사용하는 프로그래밍 언어의 문법, 특히 배열 인덱싱 및 조작에 대해 알고 있어야 합니다.

---

문제 풀어보기 🔍

 

1. 뒤에서부터 배열 채우기:
   • nums1과 nums2 두 배열이 이미 정렬되어 있기 때문에, 뒤에서부터 배열을 채워나갑니다. 이 방법을 사용하면, 이미 정렬된 nums1의 원소들을 덮어쓰지 않으면서 nums1의 뒷부분부터 값을 채워나갈 수 있습니다.
2. 포인터 위치 설정하기:
   • nums1에서는 m-1을 가리키는 포인터를, nums2에서는 n-1을 가리키는 포인터를 설정합니다. nums1 배열의 끝(m + n - 1)에서 시작하는 세 번째 포인터도 설정합니다.
3. 값 비교 및 삽입:
   • nums1과 nums2에서 가리키는 포인터의 값을 비교하여, 더 큰 값을 nums1 배열의 세 번째 포인터가 가리키는 위치에 삽입합니다.
4. 포인터 이동:
   • 값을 삽입한 배열의 포인터는 한 칸 앞으로(또는 뒤로) 이동시킵니다.
5. 배열 소진 여부 확인:
   • nums2의 모든 원소가 nums1으로 복사될 때까지 이 과정을 반복합니다.
   • 만약 nums1의 원소를 모두 사용했지만 nums2에 남은 원소가 있다면, 그 원소들을 nums1의 앞부분에 복사합니다.
6. 종료 조건 처리:
   • 만약 nums1 또는 nums2 중 하나의 배열의 원소가 먼저 소진되면, 남은 배열의 원소들을 적절한 위치에 복사합니다.
7. 정렬 완료 확인:
   • 모든 원소가 복사되었다면, nums1 배열은 두 배열이 병합된 정렬된 상태가 됩니다.

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, j, write_index = m-1, n-1, m+n-1
        
        # nums1과 nums2의 배열에서 비교할 원소가 남아 있는 동안 확인
        while j >= 0 and i >= 0:
            if nums1[i] > nums2[j]:
                nums1[write_index] = nums1[i]
                i -= 1
            else:
                nums1[write_index] = nums2[j]
                j -= 1
            write_index -= 1
        
        # nums2에 남은 원소가 있으면, nums1에 남은 자리에 이동
        while j >= 0:
            nums1[write_index] = nums2[j]
            j -= 1
            write_index -= 1
        # nums1의 원소들은 이미 올바른 위치에 있으므로 이동할 필요 없음

 

예시를 통해 더 자세히 설명하겠습니다:

nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

• nums1의 m 위치인 인덱스 2(값은 3)와 nums2의 n 위치인 인덱스 2(값은 6)를 비교합니다.
• 6이 3보다 크므로, nums1의 인덱스 m + n - 1인 5에 6을 삽입합니다.
• nums2의 포인터를 하나 줄입니다 (인덱스 1로 이동).
• 이제 nums1의 인덱스 1(값은 2)와 nums2의 인덱스 1(값은 5)를 비교합니다.
• 이 과정을 nums2가 소진될 때까지 반복합니다.

위와 같은 방식으로 두 배열을 병합하면 nums1의 결과는 [1,2,2,3,5,6]이 됩니다.

---

결론적으로, 이 문제를 해결하기 위해서는 배열 nums1의 뒷부분에서부터 시작하여 nums1과 nums2의 원소들을 크기 순으로 비교하고 채워 나가는 투 포인터 기법을 사용하는 것이 핵심입니다. nums1의 인덱스 i와 nums2의 인덱스 j를 각각 마지막 유효한 원소부터 시작하여 감소시키면서, 더 큰 값을 nums1의 끝에서부터 채워나가는 방식으로 진행합니다. 만약 nums1의 원소를 모두 채운 후에 nums2에 남은 원소가 있다면, 그 원소들을 nums1의 남은 자리에 이동시키면 됩니다.

 

이 접근 방법은 주어진 두 배열을 효과적으로 병합하면서도, 추가적인 메모리 할당을 하지 않고 주어진 배열 nums1 내에서 문제를 해결할 수 있게 합니다. 이 알고리즘은 O(m+n)의 시간 복잡도로 실행될 수 있으며, 크기가 다른 두 정렬된 배열을 병합하는 많은 실제 상황에서도 유용하게 적용될 수 있습니다.