[Easy] LeetCode - 88. Merge Sorted Array

게시 2024/04/27

By 최세현

8 분동안 읽어봐용

Problem

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

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]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.

Example 2:

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].

Example 3:

Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1] Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.

Constraints:

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

Follow up: Can you come up with an algorithm that runs in O(m + n) time?

Solve

Approach

리트코드에서의 첫번째 문제에요.

2개의 non-decreasing order 배열을 input으로 받으면,
2개의 배열의 모든 데이터를 합친 non-decreasing order 배열 하나를 output하면 되는 간단한 문제에요.

너무 쉬운 문제이긴 하지만..

환경에 익숙해지기 (problem input, output, …)
파이썬 내장 함수 찾기
버그 해결하기 size 0 / index 0 (알고리즘 문제풀이에 흔하디 흔한 케이스,,) 등등.. 많은 문제들로 인해 거의 1시간은 걸린 것 같아요 ㅠㅠ

여튼, 저는 보자마자 정형화된 유형인 두 포인터를 떠올렸고, 바로 해답을 생각해냈습니다.

각각의 배열에서 index 0에서 시작하는 각 cursorA, cursorB를 정의한 후에 cursorA를 standard로 삼고, cursorA와 cursorB를 비교해서 cursorA의 알맞은 자리에 cursorB의 데이터를 삽입하며 cursorA와 cursorB를 점차 증가시키며 끝까지 이동시키는 것이죠.

code try 1

        
      
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        idxm = 0
        idxn = 0
        while idxm < m and idxn < n:
            if nums1[idxm] >= nums2[idxn]:
                nums1.insert(idxm, nums2[idxn])
                idxn = idxn + 1
                idxm = idxm + 1
                m = m + 1
            else:
                idxm = idxm + 1
        while len(nums1) != m:
            nums1.pop()
        nums1.extend(nums2[idxn:n])

첫 코드는 그런대로 좀… 마음에 들지는 않아요. python을 쓰면서 c/c++ 느낌의 스타일이 짙게 묻어나오고 있어요. (취업 전 백준에서 몇 백개 가량의 알고리즘 문제를 풀 때 모두 C++로 풀어대서 그런지 내 코딩스타일은 C++에 맞추어져 있는 듯 해요)

code try 1 - submission result

간단하게 제출하고 결과를 확인했는데,, 실행시간 부분에서는 조금 놀랐어요. 물론 다양한 굇수들이 python의 기상천외한 방법들로 실행시간을 단축시켜놨을 거라 예상은 했지만, while로 짠 간단한 코드가 상위 37% 시간에 밖에 들지 못했다는 것에.. 조금 놀랐어요.
(그런데 어찌보면 당연한 것 같긴 해요. pop(), insert() 등 불필요한 함수를 사용했으니. 이 코드 작성 바로 다음에 insert 와 pop 함수를 제외한 코드를 바로 작성했어요.)

그리고 Solutions에 다른 사람들이 공유해놓은 Solution은 대체 어떤 것들이 있는지 바로 첫번째 글을 봤는데.. 좀 어이가 없었네요..

first post in Solutions

이…이게 뭐지…!? 정렬 알고리즘..을 그대로 쓴.,.. 간단한 해답..

아, 물론 여러가지 복합적인 문제를 풀 때에는 C++ STL 사용이 필수적이고, 그 안에서 sort 함수도 당연히 사용하며 시간 복잡도도 계산하지만,, 요렇게 간단한 문제에 적용할 거라고는 상상도 못했어요. 한 방 얻어맞은 느낌이네요.

Submission result of first post in Solutions

시간도 꽤 준수하게 나오는 것 같고…

하긴.. 사이즈 200 정도의 아주 작고 간단한 문제에 시간은 들쑥날쑥할 것 같긴 해요. 실제로 몇 번 더 돌리면 돌릴 수록 제 해답과 sort() 함수 사용한 해답 시간이 계속 엎치락 뒤치락 하네요.

뭐… 아무튼… 사담이 길었어요. 요약해보면,,

교훈

앞으로 요런 간단한 문제에도 각 언어에서 제공하는 sort() 함수의 사용을 고려하겠지만
문제의 의도를 보고, 가능한 함수의 사용을 지양하고 직접 풀어내는 로직 작성을 지향하도록 한다!
그리고.. 문제 input 크기의 규모를 보고, submission에서 제공된 runtime ms는 무시하도록 한다.

로 생각해야겠어요.

code try 2

        
      
class Solution(object):
    def merge(self, nums1, m, nums2, n):
        idx1 = m - 1
        idx2 = n - 1
        cursor = m + n - 1
        while cursor >= 0:
            if idx1 < 0 or (idx2 >= 0 and nums1[idx1] <= nums2[idx2]) :
                nums1[cursor] = nums2[idx2]
                idx2 = idx2 - 1
            else:
                nums1[cursor] = nums1[idx1]
                idx1 = idx1 - 1
            cursor = cursor - 1

code try 2 - submission result

시간복잡도를 좀 더 줄여보고자 python list의 pop과 insert 함수를 사용하지 않고 해봤어요.
오히려 시간이 늘어나는 기현상이 발생했지만.. 아까 얻은 교훈 따라서.. runtime은 신경쓰지 않기로 했어요.

Conclusion

교훈을 얻었어요.
Obsidian 사용이 익숙치 않아서 인지.. 이 간단한 글 작성에도 1시간은 쏟은 것 같아요.
그래도 뿌듯하네요. 첫번째 LeetCode Solve 글.

Leet Code, Top Interview 150

LeetCode TopInterview150