[LeetCode] 88. Merge Sorted Array

Merge Sorted Array - LeetCode

 

int형 배열 num1, num2가 0을 제외하고 오름차순 상태로 주어지고
각각의 배열의 유효한 숫자범위 m,n가 주어집니다.

즉, 주어진 배열과 m,n이 아래와 같다면

nums1 = [-1,0,0,3,3,3,0,0,0] m = 6, num2 = [1,2,3] n = 3

nums1배열의 6번째인덱스 까지가 유효한 범위입니다.

유효한 배열의 범위

nums1 = [-1,0,0,3,3,3]

nums2 = [1,2,3]

 

이 조건은 파악하지 못해 이상한 짓을 많이 했습니다...하하하

여러번의 실패를 겪으며 테스트케이스를 확인 후 문제를 간단하게 풀 수 있었습니다.  

문제접근법

두 배열을 nums1에 합치고, 정렬을 하면 되는 문제입니다.

그리고 배열의 유효한 범위는 m,n을 통해 확인할 수 있습니다.

 

처음에는 Two Pointer를 사용해서 하나씩 넣으려고 했지만 굳이?

라는 생각이 들었습니다.

 

그냥 nums1의 유효한 범위 이후부터 nums2의 값을 채워주면 됩니다.

예외처리할것도 없이 유효한 값들만 주어지니 당연히 통과할것이라고 생각했습니다.

 

수도코드

 

수도코드를 코드로 옮겨 통과를 받았습니다.

    public void merge(int[] nums1, int m, int[] nums2, int n) {

        for (int i = 0; i < m+n; i++){
            if (i < m) continue;
            nums1[i] = nums2[i-m];
        }
        Arrays.sort(nums1);
    }

 

코드개선

n까지만 반복문을 돌고 nums1의 유효범위를 지난 m+1부터 값을 채운다면 불필요한 분기문을 제거할 수 있습니다.

    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);
    }

 

❓시간복잡도 / 공간복잡도

시간복잡도

먼저 for문은 보면 n만큼 반복됩니다.

nums2의 길이인 n만큼만 돌면서 nums1의 뒤에 붙여주기만 하기때문에 for문의 반복은 n입니다.

 

하지만 정답조건을 맞추기 위해 nums1을 sort하였습니다.

만약 sort의 범위가 n보다 크다면 sort의 시간복잡도가 제가 작성한 시간복잡도가 될것이고

n이 더 크다면 O(n)이 시간복잡도가 될것입니다.

 

Sort의 시간복잡도

자바는 배열을 정렬할때 Arrays클래스의 Sort메서드를 제공합니다.

그리고 저는 Arrays클래스의 sort를 사용했습니다.

 

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 all data sets, and is typically faster than traditional (one-pivot) 
Quicksort implementations.
public static void sort(int[] a) {
	DualPivotQuicksort.sort(a, 0, 0, a.length);
}

자바의 정렬은 듀얼피봇퀵정렬(Dual-Pivot Quick Sort)을 사용한다는것을 확인할 수 있습니다.

듀얼피봇퀵정렬(Dual-Pivot Quick Sort)은 피봇 1개를 사용하는 퀵정렬과 달리 피봇 2개를 사용하여 정렬합니다.

 

문서에 보면 피봇을 1개사용하는 Quicksort보다 일반적으로 빠르다고 합니다.알려진 듀얼피봇퀵정렬의 평균 시간복잡도는 O(nlogn)입니다.

 

최악의경우 O(n2)이 걸릴수도 있다고 합니다.

평균의 경우 O(n long n)입니다.

 

공간복잡도

공간복잡도는 n+m입니다.

다른 배열이나 변수를 만들지 않고 nums1의 배열에 값을 바로 할당하기 때문입니다.

 

다른 사람들의 풀이

투 포인터를 활용하여 배열을 새로만들지 않고 뒤에서 부터 값을 집어넣는 방식입니다.

정렬 자체를 사용하지 않고 각 배열이 정렬되어있다는것을 이용해

뒤에서부터 nums1과 nums2를 비교하여 nums1에 큰값부터 채우는 방식으로
공간복잡도와 시간복잡도를 최소화 하였습니다.

 

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int tail1 = m - 1, tail2 = n - 1, finished = m + n - 1;
        while (tail1 >= 0 && tail2 >= 0) {
            nums1[finished--] = (nums1[tail1] > nums2[tail2]) ? 
                                nums1[tail1--] : nums2[tail2--];
        }

        while (tail2 >= 0) {
            nums1[finished--] = nums2[tail2--];
        }
    }

While문이 tail2만 신경쓰는 이유는 tail1이 남았을 경우에는 어차피 nums1에 정렬이 되어있기 때문입니다.

 

시간복잡도

시간복잡도는 O(m+n) 입니다.

 

공간복잡도

기존의 nums1을 사용하기때문에 공간복잡도 역시 O(m+n) 입니다.

 

마무리

리트코드문제를 풀어보았는데 영어공부를 더 열심히 해서 지문을 잘 파악해야겠다는 생각과

정렬에 대해 더 잘 알아볼 수 있는 시간이였습니다.

 

또한 무작정 정렬을 사용할 생각말고 지문을 정확히 이해하여

더 효율적으로 접근하는 방법을 생각해야겠다고 느겼습니다.

 

참고

What is the complexity of dual-pivot Quicksort?

[Dual-Pivot Quick Sort] 두 개의 피봇으로 퀵 정렬

 

What's the difference of dual pivot quick sort and quick sort?

자바 [JAVA] - 퀵 정렬 (Quick Sort)