LeetCode 88(Merge Sorted Array, Python)

1. 문제 링크

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

2. 문제 설명

• 오름차순 정수로 구성된 두 array nums1, nums2와, 각 array의 개수를 m,n이라고 할 때,
• nums1, nums2를 오름차순 순서로 merge한 list를 반환 
• 전제조건 "in-place" 
  • return하는 list는 nums1에 store해야 하며, 결과적으로 nums의 길이는 m+n이 됨
• 예시1) nums1 = [1,2,3,0,0,0] m=3, nums2 = [2,5,6] n= 3 → [1,2,2,3,5,6] 반환 
• 예시2) nums1 = [1] m=1, nums2 = [] n= 0 → [1] 반환

3. 처음 풀이 

• nums1의 m+1~m+n 자리에 nums2 element를 추가, nums2의 n+1~m+n자리에 nums1 element 추가
  • ex) nums1 = [1,2,3], nums2 = [2,5,6]일 때 일단 nums1 를 [1,2,3,2,5,6]으로, nums2를 [2,5,6,1,2,3]으로 셋팅 
• 그리고 nums1의 element에 순차적으로 min(nums2)를 append

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.
        """

        j=0
        for i in range(m,m+n): # nums1의 m+1~m+n 자리에 nums2 element를 추가
            nums1[i] = nums2[j]
            j+=1

        for i in range(m): # nums2의 n+1~m+n자리에 nums1 element 추가
            nums2.insert(i,nums1[i])

        j = 0
        for i in range(m+n): #nums1의 element에 순차적으로 min(nums2)를 append
            nums1[j] = min(nums2)
            nums2.remove(min(nums2))
            j+=1

 

• runtime beats 82.29% 로 결과 괜찮았음

4. 다른 풀이 

• 다른 사람의 풀이 중 괜찮았던 풀이
• list.sort()를 생각하지 못했었다. 단순히 nums1에 nums2 element를 넣고, nums1를 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(m, len(nums1)):
            nums1.pop(m)
        nums1 += nums2[:n]
        # for i in range(n):
        #     nums1.append(nums2[i])
        nums1.sort()

5. 배운 점 

• sort()는 in-place 방식
  • sort() 기존의 리스트를 정렬, sorted()는 새로 정렬된 리스트를 만듦.