[leetcode][python] Merge Sorted Array

---

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

 

Example 1:

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1]

 

Constraints:

• 0 <= n, m <= 200
• 1 <= n + m <= 200
• nums1.length == m + n
• nums2.length == n
• -109 <= nums1[i], nums2[i] <= 109

---

문제 설명: 

정렬된 정수형 array인 nums1, nums2가 주어지고, nums2를 nums1에 합쳐 하나의 정렬된 array를 만든다. 

nums1과 nums2의 원소 수는 각 n, m.이다. 

nums1은 nums2가 채워질 수 있게 n + m의 충분한 공간을 가진다.

 

문제 해설:

단순하게 for문을 돌려, nums1의 빈자리에 nums2 원소들의 값을 넣는다.

그 후, sort()를 사용하여 정렬한다. 

 

코드:

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.
        """
        for i in range(n):
            nums1[m + i] = nums2[i]
            
        nums1.sort()

 

59 / 59 test cases passed.

Status: Accepted

Runtime: 32 ms

Memory Usage: 14.3 MB

Submitted: 0 minutes ago

 

다른 사람의 코드:

Runtime이 16ms인 코드:

temp를 별도로 사용해서 Memory Usage는 증가했을 것 같다.

nums1의 원소들과 크기 비교를 한다.

nums2[0]은 nums2의 원소들 중 가장 작은 값이다.

따라서, nums1[i]의 값보다 같거나 크다면 nums[i]를 저장하고, 아니라면 nums2[0]을 저장한다.

전자라면 i를 1 증가시켜 다시 비교를 하고, 후자라면 index를 1증가시켜 nums1[i]와 비교한다.

i가 m(nums1의 원소 수)보다 작다면, nums1의 원소들 중 nums2보다 큰 원소들이 있어, temp에 저장되지 못한 것이다. 

즉, num2의 원소들은 temp에 다 저장되었으나, nums1의 원소들 중 일부가 저장되지 못한 것이다.

따라서 nums1의 남은 원소들을 temp에 저장한다.

j도 마찬가지이다. (nums1의 원소가 남아있었다면 수행되지 않는다.)

temp에는 합쳐진 정렬된 배열이 저장되어 있으므로 for문으로 nums1에 값을 넣는다. 

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.
        """
        #nums1[len(nums1)-len(nums2):] = nums2
        #nums1.sort()
        temp = [0]*(m+n)
        
        i,j = 0,0
        cursor = 0
        while i<m and j<n:
            if nums1[i]<=nums2[j]:
                temp[cursor] = nums1[i]
                i+=1
                cursor+=1
            else:
                temp[cursor] = nums2[j]
                j+=1
                cursor+=1
                
        while i<m:
            temp[cursor] = nums1[i]
            i+=1
            cursor+=1
            
        while j<n:
            temp[cursor] = nums2[j]
            j+=1
            cursor+=1
            
        for i in range(m+n):
            nums1[i] = temp[i]

 

 

Memory Usage가 13900 KB인 코드:

내가 작성했던 코드와 방식은 비슷하나, for문을 사용하지 않아 memory usage를 높였다.

nums1을 m(nums1의 원소의 개수)까지 slice한 후, nums2를 붙였다. 그리고 sort하여 nums1에 대입한다. 

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.
        """
        nums1[:] = sorted((nums1[:m]+nums2))

 

비고:

단순하게 생각하지 않으면 오래 걸릴거 같아서, 직관적으로 문제를 풀었다.

프로그래머스에서는 코드 양이 짧으면 좋았던 걸(Memory Usage)로 기억하는데,

리트코드에서는 Runtime를 퍼센테이지를 먼저 보여주어서 그런지, Runtime에 신경쓰게 되는 것 같다.