Intuition 🤔

뒤에서부터 채우기.

앞에서부터 채운다면 temp variable에 따로 저장해야한다. 뒤에서부터 채운다면 temp variable을 사용할 필요가 없다.

앞에서부터 채운다면 또 계속 숫자들을 움직여야한다. 하지만 뒤에서부터 채운다면 움직일 필요가 없다.

이 개념은 greedy algorithm 과도 연관이 있다. Maximum부터 먼저 선택하기 때문이다.

But.. how do I get the intuition? 😭

질문에 수상한 점들을 사용하자.

1. 왜 nums1의 뒤에 extra space가 있는가?
2. nums1과 nums2는 이미 sorting 되어있다. 이걸 어떻게 사용하지?

답안

Java

  class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int last = nums1.length - 1; 
        int index1 = m - 1; 
        int index2 = n - 1;
        while (index2 >= 0) {
            if (index1 >= 0 && nums1[index1] > nums2[index2]) {
                nums1[last] = nums1[index1]; 
                index1 -= 1; 
            } else {
                nums1[last] = nums2[index2]; 
                index2 -= 1; 
            }

            last -= 1; 
        }
    }
}

index2가 loop condition인 이유는 예시를 통해서 알 수 있다.

이렇게 nums2의 요소들이 nums1의 모든 숫자들 보다 작을때에는 nums2의 모든 숫자들을 traverse 하고 copy 할때 끝난다.

이렇게 nums1의 모든 요소들이 nums2 보다 작을때에도 nums2만 뒤에 copy하면 되기에 nums2가 loop condition이여도 된다.