[Leetcode]_88. Merge Sorted Array (Two Pointer)

문제

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

LeetCode - The World's Leading Online Programming Learning Platform

어떻게 풀어야 할지 갈피를 못잡겠어서 해설을 보면서 이해해보려고 했다.

사람들이 투포인터(Two Pointer) 문제라고 하였다.

투포인터가 무엇인지 부터 알아야겠다.

Two Pointer

"Two Pointer" 기법은 배열이나 리스트 같은 연속된 데이터 구조에서 특정 조건을 만족하는 부분 집합을 찾거나 특정 값을 계산할 때 유용하게 사용된다.

이 기법의 기본 아이디어는 배열 또는 리스트에 두 개의 포인터(인덱스)를 사용하여 원하는 결과를 얻는 것이다.

자 그럼 주어진 문제에 투포인터 기법을 어떻게 사용하여 풀지 고민해보자.

풀이

0. nums2 배열을 nums1 배열에 병합시키는 것이니 nums2 요소를 모두 확인할 때까지 반복한다.
1. 각 배열은 오름차순으로 정렬되어 있기 때문에 m,n으로 나타낸 두개의 포인터(a,b)로 각 배열의 마지막 요소의 인덱스에서부터 시작하면서 값을 비교해준다.

• 이 때, nums1 배열을 수정해야하므로 수정할 인덱스(write_index)를 나타낸 변수도 설정해준다.

Q. 왜 마지막 인덱스에서부터 시작하나요?
A. 첫번째 인덱스부터 시작하게되면 중간에 nums1배열에 nums2배열 값이 병합될 때마다 nums1을 오른쪽으로 이동시켜야 하므로 비효율적이기 때문이다.

2. nums1 요소가 크면 수정할 인덱스(write_index)에 nums1 요소를, nums2 요소가 크면 수정할 인덱스에 num2 요소를 병합한다.

• nums1 요소가 병합되면, nums1 포인터를 한칸 이동한다.
• nums2 요소가 병합되면, nums2 포인터를 한칸 이동한다.
• 한번 병합을 하고 나면 수정할 인덱스(write_index)는 한칸 이동한다.

이 때 주의할 것이 nums1의 포인터가 음수가 되었을 경우도 고려해줘야한다. 음수일 때를 고려해주지 않으면 우리는 앞서 0번째 단계에서 nums2 포인터로만 반복문을 실행하고 있기 때문에, 무한루프에 빠지거나 오류를 발생시킬 수 있기 때문이다.

정답 코드

def merge(nums1,nums2,m,n):
    a,b,write_index = m-1,n-1,m+n-1

    while b >= 0:
        if a >= 0 and nums1[a] > nums2[b]:
            nums1[write_index] = nums1[a]
            a -= 1
        else:
            nums1[write_index] = nums2[b]
            b -= 1

        write_index -= 1