[알고리즘, Python] Leetcode - 정렬된 두 배열을 합하는 문제(Merge Sorted Array)

이미 정렬된 두 개의 배열을 병합하는 문제를 풀어보자.

 

Leetcode에서 문제보기

 

---

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

문제에서는 정렬된 두 배열 nums1, nums2 그리고 각 배열의 길이인 m과 n이 주어진다.

 

nums1의 길이는 m+n이다.

 

이 문제는 기존 병합 정렬 코드보다 더 간단하다.

(병합 정렬에 대해 알아보기 : https://jwdevv.tistory.com/3)

[알고리즘, Python] 정렬 1 - 병합 정렬(Merge Sort)

 

이미 두 배열이 정렬 되어 있기 때문에 두 배열의 값만 비교해서 정렬해주면 되기 때문이다.

 

즉 nums1과 nums2 마지막 원소부터 하나씩 비교한 후 큰 값을 추가하는 식으로 구현하면 된다.

 

아래 코드를 확인해보자.

 

Python 코드

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.
        """
        
        i1 = m-1 # nums1의 index
        i2 = n-1 # nums2의 index
        current = m+n-1 # 맨 뒷자리부터 원소 채우기
        
        while current >= 0 and i1 >= 0 and i2 >= 0:
            if nums1[i1] >= nums2[i2]:
                nums1[current] = nums1[i1]
                i1 -= 1
            else:
                nums1[current] = nums2[i2]
                i2 -= 1
            current -= 1
            
        
        for i in range(i2, -1, -1):
            nums1[i] = nums2[i]

 

while문은 직관적이다.

 

그렇다면 마지막 for loop는 왜 존재할까?

 

그 이유는 만약 nums1과 nums2를 비교하던 중 더이상 nums1에서 비교할 원소가 없으면(i1 = -1로 반복문 탈출) nums2의 원소를 옮겨줘야하기 때문이다.

 

예를 들어 nums1 = [5,6,7,0,0,0,0] nums2 = [1,2,3,4] 인 경우를 생각해보면 쉽게 이해할 수 있다.

 

그렇다면 반대로 nums2에 비교할 원소가 없는 경우(i2 = -1) 는 어떻게 될까? (예: nums1 = [1,2,3,0,0,0,0], nums1 = [5,6,7,8])

 

nums1은 이미 그 자리에 존재하므로 옮겨줄 필요가 없다.

 

+

 

이 문제에서는 기존 병합 정렬처럼 원소를 복사하여 저장하지 않아도 된다.

 

 

Leetcode 실행 결과