Merge Sorted Array

문제

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

---

풀이

1. 이미 정렬된 Array이므로, nums1, nums2의 배열에서 차례대로 요소를 가져와서 비교한 후 작은 것부터 새로운 배열에 넣는다.
2. nums1 배열을 사용해야 하므로 새로운 배열을 nums1 배열에 다시 넣는다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        //새로운 배열에 merge sort로 정렬
        int [] result = new int[m+n];
        int one = 0;
        int two = 0;
        int index=0;
        //nums1과 nums2를 차례대로 비교하여 result 배열을 채운다.
        while (one < m && two < n) {
            if (nums1[one] <= nums2[two]){
                result[index] = nums1[one++];
            } else {
                result[index] = nums2[two++];
            }
            index++;
        }

		//만약 nums1 배열을 m까지 봤다면 남은 nums2 배열은 모두 큰 숫자밖에 없다는 것이므로 순서대로 복사한다.
        if (one == m) {
            int end = n-two;
            for (int i=0; i<end; i++) {
                result[index+i] = nums2[two+i];
            }
        }

		//위에와 동일하게 남은 nums1 배열을 모두 복사
        if (two == n) {
            int end = m-one;
            for (int i=0; i<end; i++) {
                result[index+i] = nums1[one+i];
            }
        }

		//nums1에 대입해야 하므로, result의 값들을 모두 복사해준다.
        for (int i=0; i<m+n; i++){
            nums1[i] = result[i];
        }
    }
}

0ms

처음에 너무 어렵게 고민해버려서.. 푸는 데 시간이 좀 많이 걸렸다. 😢

---

sort 함수 사용하기

Arrays.sort를 사용하면 배열도 정렬할 수 있다.

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

코드는 짧지만 1ms 로 직접 merge sort를 구현하는 것보다 조금 느리다.