📚 algo-wiki

Appearance

병합 정렬 배열 (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))) ​

간단한 해결 방법:

  1. nums1에서 유효한 요소만 남김.
  2. nums2를 nums1에 추가.
  3. 최종적으로 nums1을 정렬.
typescript
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))**까지 증가.
  • 불필요한 splice() 연산이 포함됨.

2️⃣ 최적화된 접근법 (투 포인터, O(m + n)) ​

더 효율적인 방법은 뒤에서부터 병합하는 것입니다.

  • nums1의 끝에서부터 요소를 비교하여 큰 값을 마지막부터 채워 넣습니다.
  • nums1의 남은 요소와 nums2를 비교하면서 하나씩 채웁니다.

구현 코드 ​

typescript
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  let i = m - 1 // nums1의 마지막 유효한 요소 인덱스
  let j = n - 1 // nums2의 마지막 요소 인덱스
  let k = m + n - 1 // nums1의 마지막 인덱스

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

✅ 장점:

  • O(m + n) 시간 복잡도 (정렬 없이 선형 시간으로 해결 가능).
  • O(1) 추가 공간 사용 (배열을 추가로 생성하지 않고 nums1을 직접 수정).
  • 대형 데이터에서도 효율적인 성능 유지.

🛠️ 사용 예시 ​

typescript
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)으로 최적화 가능.
  • 배열을 뒤에서부터 채워넣으면 추가적인 정렬이 필요 없음.

이 방법을 숙지하면 코딩 테스트에서도 효율적인 해결법을 적용할 수 있습니다! 🚀