.leetcode(88. Merge Sorted Array)

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

 

1. 2022.04.16 시도

소요시간: 11분

 class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int last1 = m-1;
        int last2 = n-1;
        
        int index = nums1.length-1;
        
        while (last1 >=0 && last2>=0) {
            int l = nums1[last1];
            int r = nums2[last2];
            
            if (l < r) {
                nums1[index--] = r;
                last2--;
            } else {
                nums1[index--] = l;
                last1--;
            }
        }
        
        while (last2 >=0) {
            int r = nums2[last2];
            
            nums1[index--] = r;
            last2--;
        }
        
    }
}

풀이 접근 과정

non-decreasing로 정렬이 되어있기 때문에 각각의 배열에서 가장 큰수에 인덱스를 배치한다.

인덱스의 값을 비교하면서 nums1의 뒤에서부터 차례로 채워준다.

두번째 배열의 요소를 모두 사용한 경우, 어차피 첫번째 배열로 머지하는 것이기에 바로 리턴하면 된다.
반대로 첫번째 배열의 요소를 모두 사용한 경우, 두번째 배열을 첫번째 배열로 머지해야하므로 while문으로 머지하는 로직이 들어간다.

 

느낀점

• 링크노드문제 풀 때, 많이 푸는 방법이다. 배열에서 풀어보니 신선하다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형