LeetCode 88 - Merge Sorted Array

https://leetcode.com/problems/merge-sorted-array

 

LeetCode 기준 Easy 난이도의 문제입니다. 두 배열을 정렬된 상태로 변환하는 문제인데 특이하게 입력받은 nums1 배열을 정렬하는 문제입니다. nums1을 반환하는 것이 아니라 nums1 자체를 정렬하면 된다는 점을 주의해야 합니다.

또 다른 특이한 점이 있습니다. 병합 후 정렬해야 하는 문제이기 때문에 배열의 특성상 사이즈에 여유가 있어야 합니다. 따라서 nums1에 nums2가 들어갈 공간만큼 0으로 차 있는 상태입니다.

문제를 보자마자 떠오른 풀이법은 그냥 nums1의 0을 앞에서부터 nums2로 채우고 정렬하면 되는 거 아닌가? 였습니다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return; // n == 0이라는 것은 병합할 nums2가 없다는 것

        int idx = 0; // nums2의 첫 위치
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[idx++]; // nums1의 0을 앞에서부터 nums2로 채운다
        }

        Arrays.sort(nums1); //nums1 정렬
    }
}

정답 처리에는 문제가 없었습니다. 하지만 이 풀이는 시간복잡도가 O((m+n)log(m+n))으로 효율적이지도 않고 문제의 의도와도 다르다는 생각이 들었습니다.

문제에서 제대로 사용하지 않은 조건이 하나 있습니다. 바로 nums1, nums2 두 배열 모두 정렬이 돼 있는 상태라는 것입니다. 이 조건을 활용해야 합니다.

이미 정렬이 된 두 배열을 합치는 작업? merge sort에서 병합하는 과정과 유사하다는 생각이 들었습니다.

보통 병합하는 과정에서는 두 정렬된 배열에서 앞에서부터 비교하며 새로운 배열을 생성하는 과정을 반복합니다. 하지만 이 문제에서는 nums1에 합쳐야 합니다. 따라서 가장 큰 값부터 찾아 뒤에서부터 채우는 방식으로 구현하였습니다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return; // 병합할 것이 없다.
        int p1 = m - 1; // nums1의 유효숫자의 마지막 위치
        int p2 = n - 1; // nums2의 유효숫자의 마지막 위치
        int p = n + m - 1; // 빈 공간의 마지막 위치

        while (p2 >= 0) {
            // p2가 음수가 되는 순간 모든 배열을 병합한 것
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[p--] = nums1[p1--];
            } else {
                // nums2[p2] >= nums1[p1]
                nums1[p--] = nums2[p2--];
            }
        }
    }
}

이 풀이를 통해 O(m+n)의 시간복잡도로 효율적으로 풀 수 있었습니다.