LeetCode 88. Merge Sorted Array

88.Merge Sorted Array

문제

두 개의 정수 배열 nums1과 nums2가 오름차순으로 정렬되어 있으며, 또한 정수 m과 n이 주어지는데, 이는 각각 nums1과 nums2의 요소 개수를 나타냅니다.

nums1과 nums2를 오름차순으로 정렬된 하나의 배열로 병합하세요.

최종적으로 정렬된 배열은 함수에서 반환되지 않고, 대신 배열 nums1 내부에 저장되어야 합니다. 이를 위해 nums1 배열은 길이가 m + n이며, 처음 m개의 요소는 병합되어야 하는 요소들을 나타내고, 나머지 마지막 n개의 요소는 0으로 설정되어 무시되어야 합니다. 배열 nums2의 길이는 n입니다.

의사코드 또는 풀이 계획

1. nums1 배열의 길이는 nums1 길이 + nums2의 길이이다.
  - 따라서 새로운 배열을 만들 필요가 없이 nums1에 nums2의 요소들을 다 넣는다.
2. nums1 배열을 정렬한다.

풀이

• 시간 복잡도 : O((m+n)log(m+n))
  • Array.sort()를 이용한 배열의 정렬은 O(NlogN) 의 시간 복잡도를 가진다. 따라서 nums1의 요소의 개수 + nums2의 요소의 개수를 합한 m+n개 만큼의 시간 복잡도를 가지게 된다.
• 공간 복잡도 : O(1)
  • 추가적인 공간을 사용하지 않는다.

1. java

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

2. kotlin

class Solution {
    fun merge(nums1: IntArray, m: Int, nums2: IntArray, n: Int): Unit {
        for (i in 0 until n) {
            nums1[m + i] = nums2[i]
        }

        nums1.sort()
    }
}

다른 풀이

• two pointer 사용
  • 시간 복잡도 : O(m + n)
    - 정렬을 위해서 한 번의 반복문과 포인터를 이용해 두 개의 배열을 순회함과 동시에 정렬한다.
  • 공간 복잡도 : O(1)

1. nums1 배열에서 유효한 인덱스를 포인터(i)로 저장한다.
2. nums2 배열에서 유효한 인덱스를 포인터(j)로 저장한다.
3. nums1 배열에 가장 마지막 인덱스를 포인터(k)로 저장한다.
4. nums1 배열에서 가장 큰 값과 nums2 배열에서 가장 큰 값을 비교해서 큰 값은 nums1, nums2 배열 병합 시 가장 큰 요소이므로 nums1의 가장 마지막 인덱스부터 가장 앞쪽 인덱스 순으로 차례대로 위치시킨다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1;
        int j = n - 1;
        int k = m + n - 1;
        
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

새로 알게된 점

1. kotlin IntArray와 Array<Int>의 차이점
   • 둘 다 원소로 정수형을 가지는 배열이라는 점은 동일하다.
   • Byte code 변환 시 IntArray는 원소들이 Java의 primmitive type인 int로 이루어져 있고 Array<Int>는 Boxing type(Wrapper Class)인 Integer로 이루어져 있다.
   • Array<Int> : toIntArray()를 통해 IntArray로 변환 가능
   • IntArray : toTypedArray()를 통해 Array<Int>로 변환 가능