[LeetCode] 88. Merge Sorted Array

I. Description

---

II. Code

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 = 0
        j = 0
        result = []
        
        while i < m and j < n:
            if nums1[i] < nums2[j]:
                result.append(nums1[i])
                i += 1
            else:
                result.append(nums2[j])
                j += 1
                
        result.extend(nums1[i:m])
        result.extend(nums2[j:n])
        
        for k in range(m + n):
            nums1[k] = result[k]

---

III. Explanation

문제 해결 방법 설명

이 문제에서는 두 개의 정렬된 배열 nums1과 nums2를 병합해야 합니다. 가장 단순한 접근 방식은 다음과 같습니다.

nums1[:m] + nums2[:n]
nums1.sort()

하지만 이 방법은 정렬에 O((m+n)log(m+n)) 시간이 소요되므로 더 효율적인 O(m+n) 알고리즘을 사용해야 합니다.

 

핵심 포인트

1. 이미 정렬된 배열: nums1(처음 m개 요소)과 nums2 모두 이미 정렬되어 있습니다.
2. 인플레이스 수정 요구: 결과를 새 리스트로 반환하는 것이 아니라 nums1을 직접 수정해야 합니다.
3. 포인터 이용: 두 배열을 순회하면서 크기를 비교하는 방식으로 병합할 수 있습니다.

코드 분석

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    i = 0  # nums1 포인터
    j = 0  # nums2 포인터
    result = []  # 병합 결과를 임시 저장할 리스트
    
    # 두 배열을 비교하며 작은 값부터 nums1_save에 추가
    while i < m and j < n:
        if nums1[i] < nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    
    # 남은 요소들 추가
    nums1 = result + nums1[i:m] + nums2[j:n]

 

문제점 분석

이 코드의 주요 문제는 마지막 줄에 있습니다:

Python에서 함수 내에서 변수에 새 객체를 할당하면(예: nums1 = 새로운_리스트), 그 변수는 함수의 지역 범위(local scope)에서만 변경됩니다. 이것은 외부에서 전달된 원래 리스트(nums1)에 영향을 주지 않습니다.

그래서 LeetCode에서는 원래 nums1이 변경되지 않아 [1,2,3,0,0,0]이 그대로 출력되는 것입니다. 반면, VS Code에서는 아마도 함수의 반환값이나 지역 변수 nums1의 값을 출력하는 코드가 있어서 올바른 결과가 나오는 것처럼 보였을 것입니다.

 

올바른 해결 방법

인플레이스로 nums1을 수정하려면 각 인덱스의 값을 직접 변경해야 합니다:

def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
    # 병합 결과를 임시 저장
    result = []
    i = 0
    j = 0
    
    while i < m and j < n:
        if nums1[i] < nums2[j]:
            result.append(nums1[i])
            i += 1
        else:
            result.append(nums2[j])
            j += 1
    
    result.extend(nums1[i:m])
    result.extend(nums2[j:n])
    
    # 결과를 nums1에 인플레이스로 복사
    for k in range(m + n):
        nums1[k] = result[k]

이 방법은 O(m+n)의 시간 복잡도로 효율적으로 두 정렬된 배열을 병합합니다.