algorithm | array - merge sorted array

> 문제

두 개의 정렬된 배열이 있고 배열 1에 배열 2를 합쳐 정렬된 배열 1을 만드는 문제입니다.

배열 1에는 배열 2만큼의 빈 공간이 마련되어 있습니다.(예제에서는 0으로 표현)

그리고 m, n으로 각각의 배열이 가지고 있는 숫자의 갯수 정보가 있습니다.

---

> solution1

배열 1의 숫자를 모두 뒤로 미루고 2개의 index로 배열 1과 2를 비교해가며 작은 숫자부터 채워 넣는 방식입니다.

하지만 배열 1의 숫자를 뒤로 미루는 작업을 해야만 합니다.

---

> solution2

reading index가 될 두 개의 포인터를 각 배열의 가장 큰 수를 가리키도록 하고 writing index가 될 또 하나의 포인터를 배열1의 가장 끝을 가리키도록 합니다.

pin_b와 pin_c를 비교하여 큰 수인 pin_c를 pin_a에 넣고 pin_c와 pin_a를 좌측으로 한칸씩 이동합니다.

다시 pin_b와 pin_c를 비교하여 큰 수인 pin_b를 pin_a에 넣고 pin_b와 pin_a를 좌측으로 이동하는 패턴을 반복합니다.

time complexity는 배열1과 배열2의 pin이 index 0까지 이동하는데 걸리는 시간인 O(n+m)이 됩니다.

index로 접근하는 사고방식의 중요함을 기억해야겠습니다.

▶︎ code

arr1 = [1, 3, 5, 0, 0, 0]
count1 = 3

arr2 = [2, 4, 8]
count2 = 3

def merge_sorted_array(nums1, m, nums2, n):
    reading_idx_1 = m - 1
    reading_idx_2 = n - 1
    writing_idx = len(nums1) - 1

    if reading_idx_2 < 0: # arr2가 빈 배열인 경우
        return

    while 0 <= reading_idx_1 and 0 <= reading_idx_2:
        num1 = nums1[reading_idx_1]
        num2 = nums2[reading_idx_2]

        if num1 >= num2:
            nums1[writing_idx] = num1
            reading_idx_1 -= 1
            writing_idx -= 1
        else:
            nums1[writing_idx] = num2
            reading_idx_2 -= 1
            writing_idx -= 1

    # case:: arr1 = [5, 6, 7, 0, 0, 0] / arr2 = [1, 2, 3]
    while 0 <= reading_idx_2:
        num = nums2[reading_idx_2]
        nums1[writing_idx] = num
        reading_idx_2 -= 1
        writing_idx -= 1

merge_sorted_array(arr1, count1, arr2, count2)
print(arr1)

---

출처: 코드없는 프로그래밍