문제

https://leetcode.com/problems/merge-sorted-array/submissions/?envType=study-plan-v2&envId=top-interview-150

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

용어 정리

non-decreasing order : 비 내림차순

• 비 내림차순을 뜻하는데. 그럼 오름차순이 아니냐? 라고 생각할 수 있습니다.
• 그냥 오름차순이 아닌 중복을 허용하는 오름차순 이라고 이해를 해야 합니다.
• ex) 1 2 2 3 4 5

정리하자면...

• nums1, nums2 는 비내림차순 정렬이 되어 있다.
• nums1, nums2를 병합해서 비내림차순으로 정렬해야 한다.
• m = nums1에서 0이 아닌 원소 수, n = nums2.length
  • nums1에 병합하기 때문에 m != nums1.length.
• 결론적으로 nums1.length = m + n

풀이

Bad Case

만약 이해를 잘못하고 새로운 배열을 만들게 된다면 이는 출제자의 의도를 파악하지 못한것이라 할 수 있습니다.

private void badCase(int[] nums1, int[] nums2) {

    int fullLength = nums1.length;
    int[] tempArray = new int[fullLength]; // 새로운 배열을 생성함.

    int nums1Index = 0;
    int nums2Index = 0;
    for (int i = 0; i < fullLength; i++) {
    if (nums1[nums1Index] != 0 && nums1[nums1Index] <= nums2[nums2Index]) {
        tempArray[i] = nums1[nums1Index];
        nums1Index++;
    } else {
        tempArray[i] = nums2[nums2Index];
        nums2Index++;
        }
    }

    System.out.println(Arrays.toString(tempArray));
}

풀이 시작

1. 앞부분은 건드리기가 어렵다.

앞 부분의 경우에는 원소가 이미 들어가있어 순서를 바꾸기가 까다롭습니다.
그럼 쓰레기 값이 들어있는 뒤에서부터 시도하면 더 괜찮지 않을까요?

2. 뒷부분부터 시작한다면 큰 값부터 비교를 한다.

뒷부분부터 채워나가기로 했으니 당연히 큰 값을 비교해야겠죠?
시작은 유효한 index인 m - 1로 시작하겠습니다.

1st. 끝값 3, 6 비교

• nums2 의 6이 더 크기 때문에 가장 마지막 인덱스에 6을 채워넣습니다.
• 이후 nums2의 탐색 인덱스를 1 줄여나가야 그 앞의 값으로 비교가 가능하겠죠?
  
  

2nd. 다음 비교

• 이제 nums1의 3과 nums2에서 인덱스를 -1 이동한 5를 비교합니다.
• 역시 5가 더 크기 때문에 5를 채워넣습니다.
• 동일하게 인덱스를 -1 이동시킵니다.
  
  

3rd. 다음 비교

• 이번에는 num1이 더 크기 때문에 이를 채워넣습니다.
  
  

4th. 값이 같다면 nums2를 먼저 소진시키자

• 이번에는 값이 같은 상황이 나왔군요! 여기서 nums1, nums2 중 무엇을 소비할 지 선택해야 합니다.
• 생각을 해보면 nums1에 병합을 하는 것이기 때문에 조금이라도 빨리 nums2를 소진시키는게 더 유리하기 때문에 같은 값이면 nums2를 소진하는게 좋아보입니다.
• nums2의 탐색 인덱스는 이제 0을 넘어 음수로 향하기 때문에 탐색에서 제외됩니다.
  
  

5th. nums2가 소진되었다면 종료!

• 이제 탐색 대상은 nums1만이 남았습니다.
• 앞선 조건에서 생각해보아야 할 것은 nums1, nums2 모두 비내림차순으로 정렬되어 있다는 것입니다!
• 그러면 그냥 여기서 정렬을 마쳐도 비내림차순을 유지할 수 있습니다!

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int insertIndex = nums1.length - 1;
        int nums1Index = m - 1;
        int nums2Index = n - 1;

        while (nums2Index >= 0) {
            if (nums1Index >= 0 && nums1[nums1Index] > nums2[nums2Index]) {
                nums1[insertIndex--] = nums1[nums1Index--];
            } else {
                nums1[insertIndex--] = nums2[nums2Index--];
            }
        }
    }
}