88.Merge Sorted Array

 

난이도: Easy

링크: LeetCode 88

풀이 날짜: 2025/10/14

 

1. 문제 이해

두 개의 정렬된 배열 nums1과 nums2가 주어지는데, 여기서 nums1은 두 배열의 모든 원소를 담을 수 있도록 뒤쪽에 여유 공간이 있다.

 

이 조건에서 nums2의 원소를 모두 nums1 안에 병합하여 오름차순 정렬된 하나의 배열을 완성하는 것이 목표이다.

단, 추가적인 배열을 만들지 않고 in-place(제자리) 에서 해결해야 한다.

 

2. 접근 방법

처음엔 이렇게 생각할 수도 있다.

“앞에서부터 작은 값부터 비교하며 채워넣으면 되겠네?”
하지만 그렇게 하면 nums1의 원래 데이터가 덮어씌워질 위험이 있다. 즉, 아직 비교가 끝나지 않은 값이 사라질 수 있다.

따라서 뒤에서부터 큰 값을 채워넣는 방식이 훨씬 안전하고, 중요한 것은 두 배열이 이미 오름차순으로 정렬되어 있다는 것이다. 뒤에서부터 채워넣다가 하나의 배열(num2)을 모두 넣었다면, 나머지 배열(num1)은 이미 정렬되어 있다는 점을 이용한다.

여기에서 아래와 같이 세 개의 포인터를 사용한다.

let first = m - 1;         // nums1의 실제 데이터 마지막 인덱스
let second = n - 1;        // nums2의 마지막 인덱스
let current = m + n - 1;   // 최종 병합된 배열의 마지막 인덱스 (nums1의 끝)

이제 큰 값부터 비교해 nums1의 뒤에서부터 채워넣는다.

 

3. 풀이 코드

var merge = function(nums1, m, nums2, n) { 
  let first = m - 1;
  let second = n - 1;
  let current = m + n - 1;

  // nums1 은 이미 정렬되어 있으므로, nums2 가 끝난지를 기준으로 while 문 실행
  while (second >= 0) {
    if (first >= 0 && nums1[first] > nums2[second]) {
      nums1[current] = nums1[first];
      first--;
    } else {
      nums1[current] = nums2[second];
      second--;
    }
    current--;
  }

  return nums1;  
};

1. 루프 조건:  while (second >= 0)

여기서 중요한 포인트는 nums2를 기준으로 while문을 돌린다는 점이다.

 

왜 nums1이 아닌 nums2를 기준으로 할까?

• nums1의 값들은 이미 정렬된 상태다.
• 남아있는 nums2의 값들이 모두 들어와야 병합이 완료된다.
• 따라서 nums2가 빌 때(second < 0)까지만 루프를 돌면 된다.

즉, nums2에 남은 값이 있다면, 아직 병합이 끝나지 않았다. 라는 조건으로 루프를 제어하는 것이다.

2. 비교 조건:  if (first >= 0 && nums1[first] > nums2[second])

• 두 배열의 마지막 값을 비교한다.
• 더 큰 값을 nums1[current] 자리에 채운다.
• 큰 값을 넣은 쪽의 인덱스를 하나 줄인다.

이 과정을 반복하면, 결국 두 배열의 원소들이 뒤에서부터 순서대로 정렬된 형태로 nums1에 채워진다.

 

4. 정리 및 요약

포인트	설명
뒤에서부터 채우기	기존 데이터를 덮지 않고 큰 값부터 안전하게 병합 가능
루프 조건: second >= 0	nums2의 모든 값이 병합될 때까지 진행
in-place 알고리즘	추가 공간 없이 nums1 내부에서 완성

이 문제의 핵심은 단순히 두 배열을 합치는 것이 아니라, “덮어쓰지 않고 병합하는 순서”를 이해하는 것이다.

 

while (second >= 0)는 단순한 반복 조건이 아니라,

“nums2가 완전히 병합될 때까지 진행한다” 는 논리적 근거를 담고 있다.