LeetCode Merge Sorted Array 문제 풀이: 초기 코드와 공간 복잡도 개선

이번 포스트에서는 LeetCode의 Merge Sorted Array 문제를 해결한 과정을 소개합니다. 처음에는 제가 작성한 초기 코드 방식으로 문제를 해결한 후, 추가 공간 사용 문제(공간 복잡도)를 개선하여 in-place 방식으로 최적화한 과정을 다룹니다.

문제 개요

Merge Sorted Array 문제는 두 개의 정렬된 배열을 하나의 정렬된 배열로 병합하는 문제입니다.

입력:
- nums1: 크기가 m+n인 배열, 처음 m개의 요소는 유효한 값이며 나머지 n개는 추가 공간입니다.
- nums2: n개의 요소로 구성된 배열.
목표:
- nums1에 nums2의 요소들을 in-place로 병합하여 오름차순으로 정렬된 배열을 만드는 것입니다.

1. 초기 코드 접근 방식

먼저, 제가 작성한 초기 코드는 nums1의 유효한 부분을 새로운 배열(nums3)에 복사한 후, nums3와 nums2를 비교하며 작은 값부터 nums1에 채워 넣는 방식입니다.

초기 코드 예시

export function merge(
  nums1: number[],
  m: number,
  nums2: number[],
  n: number,
): void {
  const nums3 = nums1.slice(0, m);
  let i2 = 0;
  let i3 = 0;

  for (let index = 0; index < m + n; index++) {
    if (i2 >= n) {
      nums1[index] = nums3[i3++];
      continue;
    }

    if (i3 >= m) {
      nums1[index] = nums2[i2++];
      continue;
    }

    nums1[index] = nums2[i2] < nums3[i3] ? nums2[i2++] : nums3[i3++];
  }
}

이 방법은 시간 복잡도 O(m+n)로 효율적이나, nums1의 첫 m개 요소를 복사하기 위해 O(m)의 추가 공간을 사용합니다.

2. 공간 복잡도 개선: in-place 방식

문제의 in-place 조건을 완벽하게 만족하기 위해, 추가 공간 없이 nums1의 뒷부분부터 채워 나가는 방식으로 코드를 개선했습니다.
이 방식은 두 배열의 마지막 인덱스부터 비교하며, 큰 값을 nums1의 끝에 배치하는 방법으로 동작합니다. 이를 통해 공간 복잡도를 O(1)로 줄일 수 있습니다.

개선된 코드 예시

export function merge(
  nums1: number[],
  m: number,
  nums2: number[],
  n: number,
): void {
  let p1 = m - 1;         // nums1의 유효 부분 마지막 인덱스
  let p2 = n - 1;         // nums2의 마지막 인덱스
  let p = m + n - 1;      // nums1의 전체 마지막 인덱스

  while (p2 >= 0) {
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
      nums1[p] = nums1[p1];
      p1--;
    } else {
      nums1[p] = nums2[p2];
      p2--;
    }
    p--;
  }
}

이 개선된 방식의 주요 장점은 다음과 같습니다:

공간 절약: 추가 배열 없이 in-place로 작업합니다.
효율성: 두 배열의 마지막 요소부터 비교하여 한 번의 순회로 병합할 수 있습니다.

결론

초기 코드에서는 추가 공간을 사용해 문제를 해결했지만, in-place 방식으로 전환함으로써 공간 복잡도 문제를 개선할 수 있었습니다. 이번 문제 풀이를 통해 알고리즘 최적화와 효율적인 코딩의 중요성을 다시 한번 확인할 수 있었습니다.

이 글이 코딩 테스트 준비와 알고리즘 문제 해결에 도움이 되길 바랍니다!