[LeetCode] 88. Merge Sorted Array - Two Pointer(투포인터) JAVA

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

Merge Sorted Array - LeetCode

코드설명

 Two Pointer(투포인터)를 활용하는 문제입니다.

 

문제에 조건을 보면 O(N+M)안에 끝낼 수 있는 문제라고 하는데, 투포인터를 사용할경우 해당사항을 활용할 수 있습니다.

문제에서 num1 에 값을 넣어서 값을 채점한다고 나와있습니다.

 

문제예시와 함께 보면,

num1 : 1 2 3 0 0 0
num2 : 2 5 6

문제를 푸는 방식은,

1 2 3 0 0 0 에서 num1의 맨 뒷부분부터 오름차순으로 채워나가는 것 입니다.

 

1. 1 2 3 0 0 6
2. 1 2 3 0 5 6
3. 1 2 3 3 5 6
4. 1 2 2 3 5 6
   
   1. 이곳에서 num2Idx가 0 보다 작아지게 되면서 중단합니다.

문제에서 이미 오름차순으로 정렬되어있기에 해당 풀이가 가능합니다.

 

마지막으로 num1에 덮어쓰는 방식으로 진행하기에 num1은 끝까지 가지 않더라도 상관없지만,

num2 같은경우, 만약 num1에 큰 숫자들이 미리 정해져있고, 먼저 종료된다면 num2는 모두 순회하지 못합니다.

관련 예시로는,

num1 : 4 5 6 0 0 0
num2 : 1 2 3

 

이 있습니다.

 

1. 4 5 6 0 0 6
2. 4 5 6 0 5 6
3. 4 5 6 4 5 6
   1. 이곳에서 종료됩니다.
4. 추가적으로 모든 num2를 다 넣어줘서 완성시킵니다.
5. 1 2 3 4 5 6

 

 

 

코드

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int num1Idx = m - 1;
        int num2Idx = n - 1;
        int newNumIdx = n + m - 1;

        //뒤에서부터 차례대로 넣습니다.
        while(num1Idx >= 0 && num2Idx >= 0){
            if(nums1[num1Idx] > nums2[num2Idx]){
                nums1[newNumIdx--] = nums1[num1Idx--];
            }else {
                nums1[newNumIdx--] = nums2[num2Idx--];
            }
        }
        
        while(num2Idx >= 0){
            nums1[newNumIdx--] = nums2[num2Idx--];
        }

    }
}