문제

각각 m개와 n개가 오름차순으로 정렬된 nums1 배열과 nums2 배열이 있다. 이 두 배열을 오름차순으로 정렬된 하나의 배열로 만드는 것이 문제이다. 단, 정렬된 배열은 nums1에 저장되어야한다. (이를위해 nums1의 길이는 m + n으로 생성되어있다.)

첫 풀이

문제 제목을 보고 가장 먼저 떠오른 것은 merge sort 방식이다. nums1과 nums2 배열이 모두 오름차순으로 정렬되어있기 때문에 적용하기 알맞아 보였다. 하지만 nums1 배열에 바로 저장하기에는 해당 배열의 값을 이용해야되기 때문에 문제가 있어 m + n 길이의 새로운 temp 배열을 선언하고 이 배열에 결과를 저장하였다. 마지막으로 결과가 nums1 배열에 존재해야하기 때문에 temp 배열의 각 원소 값을 nums1에 넣어주었다.

이 풀이의 시간복잡도는 $O(2*(m+n))$가 된다.

import java.util.*;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] temp = new int[m + n];
        int p1 = 0, p2 = 0;

        int idx = 0;
        while (p1 < m && p2 < n) {
            if (nums1[p1] <= nums2[p2]) {
                temp[idx++] = nums1[p1++];
            } else {
                temp[idx++] = nums2[p2++];
            }
        }

        if (p1 < m) {
            for (int i = p1; i < m; i++) {
                temp[idx++] = nums1[i];
            }
        } else {
            for (int i = p2; i < n; i++) {
                temp[idx++] = nums2[i];
            }
        }

        for (int i = 0; i < m + n; i++) {
            nums1[i] = temp[i];
        }

        System.out.println(Arrays.toString(nums1));
    }
}

두번째 풀이

문제에서 nums1 배열에 결과를 저장해야한다. 첫 풀이에서는 임시의 temp 배열을 생성하여 결과를 저장하고 마지막에 다시 nums1 배열에 값을 넣어주는 방식으로 풀이하였다. 하지만 이 방식은 문제의 의도대로 푸는 것이 아닌 것같아 보였다. temp 배열을 생성하지 않고 어떻게 바로 nums1 배열에 값을 저장할지 고민했지만 떠오르는건 Arrays.sort()를 이용하는 것 뿐이었다. Arrays.sort()는 내부적으로 자바 8 기준 Dual-Pivot QuickSort를 사용하며 $O(nlog(n))$의 시간복잡도를 갖는다. 따라서 이 문제에서는 $O((m+n)log(m+n))$의 시간복잡도를 갖는다.

public static void sort(int[] a)
Sorts the specified array into ascending numerical order.
Implementation note: The sorting algorithm is a Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance, and is typically faster than traditional (one-pivot) Quicksort implementations.

import java.util.*;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = 0; i < n; i++) {
            nums1[m + i] = nums2[i];
        }

        Arrays.sort(nums1);
    }
}

결과적으로 첫 풀이보다는 시간을 단축시킬 수 있었다. 또한 temp 배열을 생성하지도 않았다. 하지만 문제에서 $O(m+n)$으로 풀 수 있다고 했는데 해당 방법은 떠오르지 않았다. 결국 다른 Solution을 참고했다.

세번째 풀이

방식은 생각보다 간단했다. 방식 자체는 첫 풀이에서 적용한 merge sort의 방식과 유사했다. 다른 점은 nums1 배열과 nums2 배열의 비교를 마지막부터 진행하며 nums1 배열의 끝부터 정렬 결과를 채우는 것이다. 이렇게 하면 임시의 temp 배열을 생성할 필요가 없으며 $O(m+n)$의 시간복잡도로 풀 수 있다.

첫 풀이에서 temp 배열은 정렬에 nums1 배열의 값을 계속 사용해야하기 때문에 생성한 배열이다. 하지만 결과값을 nums1 배열의 맨 끝부터 넣게되더라도 비교해야할 nums1의 값은 아직 살아있기 때문에 temp 배열을 생성할 필요가 없게된다.

import java.util.*;

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1; // nums1의 인덱스
        int j = n - 1; // nums2의 인덱스
        int k = m + n - 1; // 결과를 저장하는 nums1의 인덱스

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

이 세번째 풀이의 특이한 점이 한 가지 더 있다. 첫 풀이에서는 아래 과정을 통해 한 쪽 배열의 원소가 남아있을 경우 채워주는 과정을 수행했다.

if (p1 < m) {
	for (int i = p1; i < m; i++) {
    	temp[idx++] = nums1[i];
	}
} else {
	for (int i = p2; i < n; i++) {
		temp[idx++] = nums2[i];
	}
}

하지만 세번째 풀이에서는 그런 과정이 따로 없다. 코드만 봤을 때 nums2 배열의 원소만 남았을 때는 처리가 된다. 하지만 nums1 배열의 원소만 남았을 때는 따로 처리하는 과정이 없다. 그 이유는 이 문제에서 nums1 배열은 애초에 오름차순으로 정렬되어있기 때문에 어차피 제자리에 남아있을 것이기 때문이다.