[Java] 88. Merge Sorted Array

문제 파악

 

두 정수 배열 nums1 과  nums2 는 비내림차순(non-decreasing) 배열이다.

 

비내림차순 : 같은 크기의 원소가 존재할 수 있는 것
ex) 1 2 3
ex) 1 1 2

 

nums1 배열의 길이는 m+n 으로, 첫 m번째까지의 원소는 merged 되어야 하고 나머지 n개는 0으로 설정되어 있다.

 

그리고 그 n개의 0 에 nums2의 원소들이 들어가야하고 최종 결과는 비내림차순으로 반환하면 된다.

 

---

풀이

 

1️⃣ Array.sort()

가장 간단하게 떠오른 풀이이다.

 

먼저 nums1 배열의 0 부분에 nums2 배열의 원소를 입력한 후, Arrays.sort() 를 사용하는 것이다.

 

입력하는 방법은 간단하다.

 

nums1의 m+1 번째 부터 m+n번째 까지 0으로 입력되어 있으므로

 

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

위와 같은 for문을 순회하면 된다.

 

import java.util.*;
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[i - m];
        }
        Arrays.sort(nums1);
    }
}

 

💡 참고로 Arrays.sort() 는 DualPivotQuickSort 라는 알고리즘을 사용하는데,

평균 시간 복잡도는 O(NlogN) 이고 최악인 경우 O(N^2) 이라고 한다.

 

 

결과

 

 

2️⃣ 포인터 방식 (실패)

O(m+n) 으로 해결할 수 있는 방법을 고민해보았다.

 

nums1과 nums2가 둘다 정렬되어 있기 때문에

 

포인터 방식을 사용하면 좋을 것 같다는 생각이 들었다.

 

import java.util.*;
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] result = new int[m + n];

        int idx1 = 0;
        int idx2 = 0;
        for (int i = 0; i < m + n; i++) {
            if (idx1 < m && idx2 < n) {
                if (nums1[idx1] >= nums2[idx2]) {
                    result[i] = nums2[idx2++];
                } else {
                    result[i] = nums1[idx1++];
                }
            } else if (idx2 >= n) {
                result[i] = nums1[idx1++];
            } else if (idx1 >= m) {
                result[i] = nums2[idx2++];
            }
        }

        nums1 = result;
    }
}

 

이렇게 풀고나니, 잘 출력이 되어 통과할 줄 알았지만 통과하지 못했다.

 

문제에 

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. 

위와 같은 문구가 있었는데, nums1 배열의 메모리 위치가 변화하면 인정을 안해주는 것 같다.

 

따라서 다른 풀이를 생각해야 했다.

 

3️⃣ 포인터 방식

 

풀이 2와 거의 유사하게 해결할 수 있었다.

 

nums1의 뒷 부분 공간이 0으로 비워져 있기 때문에, 이 공간을 활용했다.

 

뒷 공간 부터 값을 채워나가야 하기 때문에, 

 

nums1와 nums2는 서로가 가진 가장 큰 값을 비교하고, 그 중 큰 값을 채워나가야 한다.

 

그리고, 채우는데 사용한 배열의 포인터는 1 감소시키면 된다.

 

3과 6중 6이 크므로 6이 제일 뒤에 채워지고 nums2의 포인터는 1감소할 것이다.

 

 

또, 3과 5를 비교하면, 5가 크므로 5가 채워지고 nums2의 포인터는 1 감소한다.

 

다음은, nums1의 3이 크므로 3이 채워지고 nums1의 포인터가 1 감소한다.

 

이런식으로 채워나가면 정답을 구할 수 있다.

 

import java.util.*;
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int idx1 = m - 1;
        int idx2 = n - 1;
        for (int i = m + n - 1; i >= 0; i--) {
            if (idx1 >= 0 && idx2 >= 0) {
                if (nums1[idx1] <= nums2[idx2]) {
                    nums1[i] = nums2[idx2--];
                } else {
                    nums1[i] = nums1[idx1--];
                }
            } else if (idx2 < 0) {
                nums1[i] = nums1[idx1--];
            } else if (idx1 < 0) {
                nums1[i] = nums2[idx2--];
            }
        }
    }
}

 

결과

 

 

---

📖 회고

간단한 문제라도, 시간 복잡도를 줄일 수 있는 방법이 더 없을까? 고민을 해봐야겠다.

 

그리고 Arrays.sort() 를 항상 생각없이 사용했던 것 같은데, 이 문제를 풀면서 어떤 알고리즘으로 정렬되는지, 어떤 시간 복잡도를 갖고 있는지를 알게되었다.