병합 정렬 배열 (LeetCode 88)

문제 설명

정렬된 두 개의 정수 배열 nums1과 nums2가 주어집니다. m과 n은 각각 nums1과 nums2에 포함된 요소의 개수를 나타냅니다.

nums2를 nums1에 병합하여 정렬된 하나의 배열로 만들어야 합니다. 추가적인 배열을 사용하지 않고, nums1 내부에서 해결해야 합니다.

제약 조건

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

---

풀이

1. 기본 접근법 (정렬 사용, O((m + n) log(m + n)))

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  nums1.splice(m, nums1.length - m)
  nums2.splice(n, nums2.length - n)
  nums1.push(...nums2)
  nums1.sort((a, b) => a - b)
}

단점: sort() 사용으로 시간 복잡도가 O((m + n) log(m + n))까지 증가.

2. 투 포인터 (O(m + n))

뒤에서부터 병합하여 큰 값을 마지막부터 채워넣는다.

function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  let i = m - 1
  let j = n - 1
  let k = m + n - 1

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

• O(m + n) 시간, O(1) 공간

---

사용 예시

const nums1 = [1, 2, 3, 0, 0, 0]
const m = 3
const nums2 = [2, 5, 6]
const n = 3
merge(nums1, m, nums2, n)
console.log(nums1) // 출력: [1, 2, 2, 3, 5, 6]

---

핵심 정리

• 정렬 방법은 쉽지만 비효율적
• 투 포인터로 뒤에서부터 채워넣으면 O(m + n)에 해결 가능
• 추가 배열 없이 in-place로 처리