[코테] Merge Sorted Array

문제 링크

Merge Sorted Array - LeetCode

<로직 고민/>

• leetcode는 문제를 해석하는 것부터가 일이구나...!
• 일단  nums1과 nums2를 extend 한 다음, 0을 삭제하고 .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.
        """
        nums1.extend(nums2)
        for num in nums1:
            print(num)
            if num == 0:
                nums1.remove(num)
            print(nums1)
        nums1.sort()

• 근데 이렇게 하니까 0이 한 개 삭제되지 않는다

1
[1, 2, 3, 0, 0, 0, 2, 5, 6]
2
[1, 2, 3, 0, 0, 0, 2, 5, 6]
3
[1, 2, 3, 0, 0, 0, 2, 5, 6]
0
[1, 2, 3, 0, 0, 2, 5, 6]
0
[1, 2, 3, 0, 2, 5, 6]
5
[1, 2, 3, 0, 2, 5, 6]
6
[1, 2, 3, 0, 2, 5, 6]

• print로 찍어본 건데 인덱스 3 자리에 있는 0이 사라지면서 0이 한 칸씩 앞으로 왔는데 for문으로는 인덱스 4 자리에 가있어서 인덱스 4에 있다가 3으로 옮겨진 0이 삭제되지 않는 거였다
• 그렇다면 맨 뒤 인덱스부터 순환하면 어떨까!! 라는 생각에 

for num in nums1[::-1]:

• 이렇게 수정하니 테스트를 통과했다!
• 근데 채점을 하니 실패했다
• 문제를 잘못 이해했군.. 0이 아예 없어야 하는 게 아니라 출력되는 리스트의 길이가 m+n인데 자리가 남으면 0으로 채우고 부족하면 그 길이만큼 0을 제거하는 것 같다
• while문 아래에 if문으로 nums1 길이가 m+n값보다 크면 0을 제거하고 작으면 0을 추가하고 같으면 break하고 마지막에 sort() 했더니 테스트를 통과했다
• 근데 뭔가 좋은 풀이는 아닌 듯??

---

<완성된 코드/>

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        nums1.extend(nums2)
        while True:
            if len(nums1) > (m+n):
                nums1.remove(0)
            if len(nums1) < (m+n):
                nums1.append(0)
            if len(nums1) == (m+n):
                break
        nums1.sort()

---

<다른 사람 풀이/>

- 천재풀이1

class Solution(object):
    def merge(self, nums1, m, nums2, n):
      for j in range(n):
          nums1[m+j] = nums2[j]
      nums1.sort()

• 시간복잡도 : O((m+n)log(m+n)) / 공간복잡도: O(1)
• 아 이런 간단한 방법이....
• 아니 그럼 nums1 길이가 m보다 크면 인덱스 m부터는 0인거야..????

• 걍 진작 번역해서 풀 걸 그랬다..ㅎㅎ

---

- 천재풀이2

class Solution(object):
    def merge(self, nums1, m, nums2, n):
        i = m - 1
        j = n - 1
        k = m + n - 1
        
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1

• 시간복잡도 : O(m+n) / 공간복잡도: O(1)
• 인덱스의 신이구만
• 도통 무슨 말인지 모르겠는걸...
• 그러고보니 이 풀이는 sort도 안 하네??
• if-else문에서 정렬을 하면서 merge하는 건가 보네
• 여튼 배열 문제가 나오면 인덱스를 활용하는 것도 고려해야 공간복잡도를 간단하게 할 수 있는 것 같군
• 아 또 문제에 있었네 nums1, 2는 오름차순으로 정렬되어 있다고,,,
• 그래서 맨 뒤 인덱스부터 비교해서 값을 넣는거네!!
• 근데 어떻게 이런 생각을 하는거지....