[LeetCode] Top review 150; Merge Sorted Array

Eunbi Lee·2026년 4월 26일

Algorithm

목록 보기

8/13

Problem

Merge Sorted Array

Background

각 nums1 및 nums2 의 원소 수를 나타내는 두 개의 정수 m 및 n 이 제공된다.
- 이때, nums1 및 nums2 는 비내림차순으로 정렬되어 있다.
nums1 과 nums2를 비내림차순으로 정렬된 단일 배열로 병합하자.
- nums1.length == m + n
- nums.length == n

비내림차순이란, 동일한 원소가 존재하여 정렬 시 완벽하게 오름차순으로 정렬되지 않는 순서를 의미한다.

ex. [1,2,3,2,5,6] 은 비내림차순이므로, 정렬 시 [1,2,2,3,5,6] 가 된다.

Solve

힌트

처음에 이 문제를 봤을 때, 문제의 난이도를 낮췄다고 생각된 포인트는 다음과 같았다.

nums1.length == m + n

이때, m 은 nums1 의 길이이고 n 은 nums2 의 길이이니 직접 nums1 과 nums2 의 원소를 일일히 비교할 필요가 없다고 생각했다.

nums1 의 길이는 항상 nums2 보다 클 것이고, nums1 에서 0으로 채워진 빈 자리는 nums2 의 모든 원소가 대체할 수 있음을 눈치챘기 때문이다.

엣지 케이스

근데, nums1 또는 nums2 의 원소가 없거나 0으로만 채워진 경우는 처음에 고려하지 못했다.

따라서 nums1.length 인 m 과 nums2.length n 을 활용할 생각을 못했다.

그래서 실행할 때마다 다양한 엣지 케이스에 골고루 걸려서 통과되지 못했다.

그러다가 최종적으로 아래의 엣지 케이스를 마주하고, 하나씩 덧대서 방어하는 코드를 추가하는 방향은 아닌 것 같다는 생각을 했다.

ex.
- nums1 = [0,0,0,0,0]
- m = 0
- nums2 = [1,2,3,4,5]
- n = 5

오답인 이유

처음 완성했던 코드는 다음과 같다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (nums1.length == 1) {
            List<Integer> copy = Arrays.stream(nums1)
            .boxed()
            .collect(Collectors.toList());

            if (nums2.length != 0) {
                copy.add(nums2[0]);
                copy.remove(copy.get(0));
            }

            int[] total = copy.stream()
            .mapToInt(element -> element)
            .toArray();
            
            overwrite(nums1, total);
            return;
        }

        List<Integer> copy = Arrays.stream(nums1)
        .filter(element -> element != 0)
        .boxed()
        .collect(Collectors.toList());

        int remainLoop = nums1.length - nums2.length;
        for (int index = 0; index < remainLoop; index ++) {
            copy.add(nums2[index]);
        }

        List<Integer> complete = copy.stream()
        .sorted()
        .collect(Collectors.toList());

        int[] total = complete.stream()
        .mapToInt(element -> element)
        .toArray();

        overwrite(nums1, total);
    }

    private void overwrite(int[] origin, int[] updated) {
        for (int index = 0; index < origin.length; index++) {
            origin[index] = updated[index];
        }
    }
}

그리고, nums1.length == 1 if 문 및 copy 생성 시 filter 는 엣지 케이스를 방어하기 위해 추가된 로직이었다.

하지만, 위에서 말한 것처럼 아래의 두 케이스가 세분화되었을 때 방어하지 못했다.

nums1 또는 nums2 의 원소가 없거나
- 케이스별로 IndexOutOfBounds Exception 가 반복적으로 발생했다.
nums1 가 0으로만 채워져 있거나
- 케이스별로 int[] 을 List 로 생성 시, 원소 개수가 부족한 빈 리스트로 생성될 수 있었다.

수정한 코드

곰곰히 생각해보았을 때, 결국 두 케이스는 m 과 n 을 활용하면 해결할 수 있었다.

int[] 를 List 로 생성 시, 유효한 원소(0이 아닌 원소)를 의미하는 m 의 개수를 가진 리스트를 생성하면 된다.
nums2 의 원소를 모두 추가하기 위해, n 만큼 loop 를 순회하여 추가하면 된다.

  class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        List<Integer> copy = Arrays.stream(nums1)
        .limit(m)
        .boxed()
        .collect(Collectors.toList());

        for (int index = 0; index < n; index++) {
            copy.add(nums2[index]);
        }

        List<Integer> complete = copy.stream()
        .sorted()
        .collect(Collectors.toList());

        int[] total = complete.stream()
        .mapToInt(element -> element)
        .toArray();

        overwrite(nums1, total);
    }

    private void overwrite(int[] origin, int[] updated) {
        for (int index = 0; index < origin.length; index++) {
            origin[index] = updated[index];
        }
    }
}