[A100C_day 2] Leetcode 88. Merge Sorted Array (java)

---

문제 링크

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

LeetCode - The World's Leading Online Programming Learning Platform

 

문제 분석

1. 주어진 인자는 sorted array인 nums1, nums2 그리고 각각이 이들의 요소 개수인 m, n 

2. 앞으로 보나 뒤로 보나 two pointer로 풀면 될 것 같다!

3. 중요한 점은 새로운 배열을 리턴하는 것이 아닌, nums1 배열을 조건에 맞게 변경시켜 주는 것!(보통 해외 코테에 이런 유형이 많다고들 한다.)

 

---

Solution 1. sort() 메서드 활용

ㅋㅋ.. 

그냥 하나로 합쳐서 sort() 메서드 활용.. 

 

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

 

문제에서 추가로 요구하는 O(m+n)의 시간 복잡도를 만족하지는 못하지만, 

sort()메서드의 시간 복잡도는 O(n log n) 이므로,, O(m+n log m+n)의 시간 복잡도를 갖는다는 것만 파악후 빠르게 넘어가자!

 

그렇다면 O(m+n)의 time-complexity를 위해서는..

 

---

Solution 2. Three Pointer

기존의 nums1배열만 수정해주면 되므로, nums1의 요소를 복사하는 새로운 배열 nums1Copy를 생성하여 접근해줬다!

 

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
    	//nums1Copy 배열에 값 복사
        int[] nums1Copy = new int[m];
         for (int i = 0; i < m; i++) {
            nums1Copy[i] = nums1[i];
        }
        
        int idx1 = 0, idx2 = 0;
        
        for(int i = 0; i < m + n; ++i){
            if(idx2 >= n || (idx1 < m && nums1Copy[idx1] < nums2[idx2])){
                nums1[i] = nums1Copy[idx1++];
            }else {
                nums1[i] = nums2[idx2++];
            }
        }
        
    }
}

 

idx1, idx2, i 세 인덱스로 케이스 나눠 비교하면 되는 간단한 알고리즘!!

(이제와 생각해보니 i 보다는 다른 변수명을 쓰는게 더 나았을 것 같기도..?)

 

문제 요구대로 O(m+n)의 시간복잡도와, O(m) 정도의 공간복잡도를 갖는 알고리즘!

내일은 오랜만에 dp 풀어볼 예정