Merge Sorted Array — 뒤에서부터 채우는 제자리 병합

정렬된 두 배열을 nums1 안에서 합치기, 어떤 문제인가요?

LeetCode 88번 문제는 이렇게 주어집니다.

오름차순으로 정렬된 두 정수 배열 nums1, nums2와 정수 m, n이 주어집니다. nums1의 처음 m개 원소와 nums2의 n개 원소를 합쳐, 오름차순으로 정렬된 하나의 배열로 만드세요. 결과는 새로 반환하지 않고 nums1 안에 저장해야 합니다.

여기서 nums1의 길이는 m + n이며:

• 앞의 m개는 실제 값
• 뒤의 n개는 0으로 채워진 빈 자리

입니다.

예시는 이렇습니다.

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

제약은 다음과 같습니다.

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -10^9 <= nums1[i], nums2[j] <= 10^9

문제의 follow-up은 O(m + n)으로 풀 수 있는가입니다.

핵심은 nums1 뒤쪽에 이미 빈 공간이 준비되어 있다는 점입니다. 이 글에서는 별도 배열을 쓰는 직관적인 풀이부터, 왜 앞에서부터 병합하면 안 되는지, 그리고 뒤에서부터 채우는 제자리 O(m + n) 풀이까지 정리하겠습니다. 시간·공간 복잡도 표기가 익숙하지 않다면 시간 복잡도와 공간 복잡도 완전 정복을 먼저 읽어 보시는 것을 권합니다.

문제를 다시 해석해 보기

첫 번째 예시를 보겠습니다.

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

여기서 실제로 병합해야 하는 대상은:

nums1의 앞 3개: [1, 2, 3]
nums2 전체   : [2, 5, 6]

입니다. nums1의 뒤쪽 0, 0, 0은 값이 아니라 빈 슬롯입니다.

즉 문제는 사실상:

정렬된 두 배열 [1, 2, 3]과 [2, 5, 6]을 병합하되
결과를 nums1의 전체 공간 [_, _, _, _, _, _]에 써라

로 볼 수 있습니다.

Phase 1. 새 배열에 병합한 뒤 nums1에 복사하기

가장 직관적인 방법은 새 배열을 하나 만들고, 일반적인 merge를 수행한 다음 nums1에 복사하는 것입니다.

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
    val merged = IntArray(m + n)
    var i = 0
    var j = 0
    var k = 0

    while (i < m && j < n) {
        if (nums1[i] <= nums2[j]) {
            merged[k++] = nums1[i++]
        } else {
            merged[k++] = nums2[j++]
        }
    }

    while (i < m) merged[k++] = nums1[i++]
    while (j < n) merged[k++] = nums2[j++]

    for (index in merged.indices) {
        nums1[index] = merged[index]
    }
}

첫 번째 예시에서는:

[1, 2, 3] 과 [2, 5, 6]을 병합
-> [1, 2, 2, 3, 5, 6]

을 만든 뒤, 이를 nums1에 복사합니다.

이 방식은 이해하기 쉽고 정답도 맞습니다. 시간 복잡도는 O(m + n)입니다. 다만 merged 배열 때문에 추가 공간이 O(m + n) 듭니다. 문제는 결과를 nums1에 직접 저장할 수 있는 구조를 주었으므로, 이 공간을 아낄 수 있습니다.

왜 앞에서부터 직접 병합하면 안 되나요?

nums1 안에 바로 써 보려고 앞에서부터 병합하면, 아직 읽지 않은 값을 덮어쓸 수 있습니다.

예를 들어:

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

에서 앞에서부터 쓰기 시작하면:

• 1은 괜찮습니다
• 다음 자리에 2를 넣는 순간
• 원래 nums1에 있던 뒤쪽 값들이 섞이기 시작합니다

더 작은 예시로 보면 더 분명합니다.

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

정답의 맨 앞은 1이어야 합니다. 그런데 nums1[0] = 1을 쓰는 순간, 원래 nums1[0]에 있던 4를 잃어버립니다. 아직 그 값은 뒤쪽 어디에 들어가야 할지 처리도 못 했는데 말입니다.

즉 앞에서부터 쓰면:

• 읽기 대상과 쓰기 대상이 충돌하고
• 아직 처리하지 않은 원래 값을 덮어쓸 위험이 있습니다

이 문제를 피하려면 아직 아무 값도 없는 뒤쪽 빈 공간부터 채워야 합니다.

Phase 2. 뒤에서부터 채우기

가장 큰 값은 두 배열의 맨 끝 중 하나에 있습니다. 따라서 결과 배열의 맨 뒤부터 채우면 덮어쓰기 문제 없이 병합할 수 있습니다.

포인터는 이렇게 둡니다.

• i = m - 1: nums1의 실제 마지막 원소
• j = n - 1: nums2의 마지막 원소
• write = m + n - 1: nums1의 마지막 칸

fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int) {
    var i = m - 1
    var j = n - 1
    var write = m + n - 1

    while (j >= 0) {
        if (i >= 0 && nums1[i] > nums2[j]) {
            nums1[write] = nums1[i]
            i--
        } else {
            nums1[write] = nums2[j]
            j--
        }
        write--
    }
}

첫 번째 예시를 따라가 봅시다.

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

i = 2 (3), j = 2 (6), write = 5
3 vs 6 -> 6이 더 큼 -> nums1[5] = 6

i = 2 (3), j = 1 (5), write = 4
3 vs 5 -> 5가 더 큼 -> nums1[4] = 5

i = 2 (3), j = 0 (2), write = 3
3 vs 2 -> 3이 더 큼 -> nums1[3] = 3

i = 1 (2), j = 0 (2), write = 2
2 vs 2 -> nums2 쪽을 써도 됨 -> nums1[2] = 2

j < 0가 되면 종료

결과는:

[1, 2, 2, 3, 5, 6]

입니다.

시간 복잡도는 O(m + n)이고, 추가 공간은 포인터 몇 개뿐이므로 O(1)입니다.

왜 while (j >= 0)만 보면 되나요?

이 구현에서 핵심은 nums2의 값이 모두 들어가기만 하면 끝난다는 점입니다.

두 경우를 나눠 보면:

1. nums1 값이 먼저 다 소진되는 경우 이때는 남은 nums2 값을 계속 복사해야 하므로 반복이 더 필요합니다.

2. nums2 값이 먼저 다 소진되는 경우 이때 nums1의 남은 값들은 이미 제자리에 있습니다.

예를 들어:

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

이면 뒤에서 6, 5, 4를 채운 뒤 종료하면 되고, 앞쪽 [1, 2, 3]은 손댈 필요가 없습니다.

그래서 반복 조건을:

while (j >= 0)

만 두면 충분합니다. nums1 쪽 잔여 처리를 따로 쓸 필요가 없습니다.

같은 값이면 어느 쪽을 먼저 써도 되나요?

됩니다. 이 문제는 최종적으로 정렬만 맞으면 되기 때문입니다.

예를 들어 nums1[i] == nums2[j]라면:

• nums1 쪽 값을 먼저 써도 되고
• nums2 쪽 값을 먼저 써도 됩니다

현재 구현은:

if (i >= 0 && nums1[i] > nums2[j]) { ... } else { ... }

이므로 같을 때는 nums2[j]를 씁니다. 정렬 결과에는 문제가 없습니다.

엣지 케이스

자주 확인해 볼 만한 입력은 이렇습니다.

입력	결과	이유
nums1=[1], m=1, nums2=[], n=0	[1]	두 번째 배열이 비어 있음
nums1=[0], m=0, nums2=[1], n=1	[1]	첫 번째 배열의 실제 값이 없음
nums1=[2,0], m=1, nums2=[1], n=1	[1,2]	더 작은 값이 nums2에 있음
nums1=[1,2,3,0,0,0], m=3, nums2=[2,5,6], n=3	[1,2,2,3,5,6]	기본 예시
nums1=[4,5,6,0,0,0], m=3, nums2=[1,2,3], n=3	[1,2,3,4,5,6]	앞에서부터 쓰면 위험한 대표 예시

특히 m = 0인 경우가 중요합니다. 이때는 nums1의 앞쪽 값은 전부 무시해야 하고, 사실상 nums2를 그대로 복사하는 문제가 됩니다.

두 풀이를 다시 비교

풀이	시간	공간	특징
새 배열에 병합 후 복사	O(m + n)	O(m + n)	가장 직관적이지만 추가 공간이 필요
뒤에서부터 제자리 병합	O(m + n)	O(1)	nums1의 빈 공간을 활용하는 최종 풀이

마무리

1. 이 문제는 정렬된 두 배열의 병합 문제이지만, 결과를 nums1 안에 저장해야 합니다 — 뒤쪽 0들은 값이 아니라 빈 공간입니다
2. 앞에서부터 직접 쓰면 아직 읽지 않은 nums1 값을 덮어쓸 수 있습니다 — 그래서 정면으로 병합하면 안 됩니다
3. 가장 큰 값은 항상 두 배열의 끝 중 하나에 있습니다 — 이 점 때문에 뒤에서부터 채우는 전략이 성립합니다
4. while (j >= 0)만으로 충분합니다 — nums2가 소진되면 nums1의 남은 값은 이미 제자리에 있기 때문입니다
5. 최종 제자리 풀이는 O(m + n) 시간, O(1) 공간입니다 — 이 문제의 핵심은 빈 공간을 단순 저장소가 아니라 병합 버퍼로 보는 관점입니다