Leetcode 88. Merge Sorted Array

제일 처음에 냈던 답변.

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.
        """
        cnt = {}

        for i in nums1[:m]:
            if i in cnt.keys():
                cnt[i] += 1
            else:
                cnt[i] = 1
        for i in nums2:
            if i in cnt.keys():
                cnt[i]+= 1
            else:
                cnt[i] = 1

        idx = 0
        for i in cnt.keys():
            for _ in range(cnt[i]):
                nums1[idx] = i
                idx += 1

공개 테스트케이스는 모두 통과했으나 막상 제출해보니 25/59개만을 통과했다.

틀린 테스트케이스를 확인해 보니 nums1이 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.
        """
        cnt = {}

        for i in nums1[:m]:
            if i in cnt.keys():
                cnt[i] += 1
            else:
                cnt[i] = 1
        for i in nums2:
            if i in cnt.keys():
                cnt[i]+= 1
            else:
                cnt[i] = 1

        cnt = dict(sorted(cnt.items()))

        idx = 0
        for i in cnt.keys():
            for _ in range(cnt[i]):
                nums1[idx] = i
                idx += 1

중간에 cnt = dict(sorted(cnt.items()))를 추가해줬더니 다 통과하긴 했는데 시간을 많이 썼다. (당연함) 그래서 다른 답변들을 보니

1. nums1의 뒤부터 시작
2. i (nums1), j (nums2), k (nums1의 가장 큰 숫자) 사용
3. i와 j를 비교해 큰 값을 k에 저장하고 k -=1
4. i와 j 중 큰 값을 가지고 있던 인덱스를 i -= 1 or j -= 1
5. i와 j 중 하나가 -1이 되면 -1가 아닌 인덱스를 가진 배열을 그대로 k에 저장 & k -= 1 반복