[리트코드] Merge Sorted Array(python)

리트코드, Merge Sorted Array_정렬된 배열 병합

 

TL;DR

• 배열을 문제에 제시된 조건에 맞게 해결할 수 있는지

문제 분석

1. m과 n의 유효한 원소를 갖고 있는 비내림차순으로 정렬된 정수 배열 nums1와 nums2
2. nums1과 nums2를 nums1에 비내림차순으로 정렬하여 합쳐야 한다.
3. 정렬된 답은 nums1에 저장되어야 한다.
4. nums1은 m + n길이를 갖고 있으며 첫 번째, m개 만큼이 정렬의 대상이 되는 정수들이다.
5. nums2는 n길이를 갖고 있으며, n이 0이라면 무시한다.

 

- 비내림차순(non-decreasing order) : 오름차순과는 다른 개념이다. nums1과 nums2에서 같은 원소가 있을 때는 nums1의 원소가 nums2의 원소보다 앞서 있어야 한다.

- 3 : 정답을 반환하는 형태가 아닌 nums1에 합쳐주기만 하면 된다.

- 4 ~ 5 : 입출력 형태를 통해 확인할 수 있는 문제의 조건들이다.

입출력 형태

입출력 예시

 

- 예시 1

    - nums1의 m번째 수인 1, 2, 3은 정렬이 되어야 하는 대상이다.

    - 나머지 원소인 0, 0, 0은 nums2로 채워저야 하는 공간이다.

    - 두 리스트를 nums1에 합친 형태인 [1, 2, 2, 3, 5, 6]이 되어야 한다.

- 예시 2 : n = 0인 경우는 nums2에 유효한 수가 없으므로 nums1을 반환하면 된다.

- 예시 3 : m = 0인 경우, nums1에 유효한 수가 없는 것이므로 nums2의 원소를 nums2에 넣으면 된다.

풀이

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # num1과 nums2의 마지막부터 비교해서 큰 값부터 num1에 넣는다!
        last = m + n - 1
        nums1_last = m - 1
        nums2_last = n - 1
        
        while last >= 0:
            if nums2_last < 0 or (nums1_last >=0 and nums1[nums1_last] >= nums2[nums2_last]):
                nums1[last] = nums1[nums1_last]
                nums1_last -= 1
            else:
                nums1[last] = nums2[nums2_last]
                nums2_last -= 1
            last -= 1

 

- 오름차순 조건이라면 nums1에 0인 자리에 nums2를 넣은 후, sort() 또는 sorted()를 사용하면 되지만, 비내림차순이라는 조건으로 인해 사용할 수 없다. 또한, 문제 조건에서 함수를 사용하여 정렬한 리스트를 반환하지 말라고 되어 있다.

 

- nums1과 nums2가 비내림차순으로 정렬된 리스트이기 때문에, 가장 큰 원소인 m-1, n-1번째 인덱스를 서로 비교하여 m + n - 1부터 채워나가면 된다. 투 포인터를 사용한다고 생각하면 된다.

- last : 합쳐야 하는 nums1의 마지막 원소를 의미한다. 두 배열에서 가장 큰 수가 들어가게 된다.

- nums1_last, nums2_last : 두 배열에서 유효한 정수 중 가장 큰 수의 인덱스이다.

- last가 0보다 작지 않을 때까지, 즉 정렬이 완료될 때까지 아래 과정을 반복한다.

    - num1의 원소가 들어가는 경우는 총 2가지이다.

       1. nums1가 유효한 정수(0 이상의 인덱스)이며, 해당 인덱스의 정수가 nums2의 정수보다 클 때

       2. 모든 nums2의 원소가 nums1보다 커서 이미 nums1에 들어간 상태일 때

    - if 구문에 있는 조건들이 위 2가지를 의미한다.

    - 나머지 경우는 nums2의 원소를 nums1의 뒤부터 채운다.

    - 정수를 합친 이후에는 각각의 포인터들을 1씩 줄여, 작은 숫자로 이동해야 한다.