88. Merge Sorted Array

문제 링크: https://leetcode.com/problems/merge-sorted-array/?envType=study-plan-v2&envId=top-interview-150

주어진 조건

• 2개의 정수 배열: num1, nums2 (오름차순으로 정렬된 상태)
• num1과 num2의 요소 개수를 나타내는 정수: m, n

문제

nums1과 nums2를 하나의 배열로 합치자. (단, 오름차순으로 정렬)

고려사항

• 수행 결과인 배열은 return 하지 않는 대신, nums1에 저장되어 있어야 한다.

나의 풀이

보자마자 든 생각은 하나로 합친 다음에 정렬하면 되지 않을까? 라는 생각이 들었다.

슬라이싱을 사용하지 않고 그냥 단순하게 for문을 실행하도록 짰다.

nums1[m] 부터 nums2[0]의 요소를 하나씩 넣어 nums1 끝에 nums2 리스트가 합쳐지도록 한 후, sort() 함수를 사용해 nums1 리스트를 정렬했다.

구현 코드

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        for i in range(m,m+n):
            nums1[i]=nums2[i-m]
        nums1.sort()

결과

다른 풀이

def merge_two_sorted_arrays(A: List[int], m: int, B: List[int], n: int) -> None:
    a, b, write_index = m-1, n-1, m + n - 1

    while b >= 0:
        if a >= 0 and A[a] > B[b]:
            A[write_index] = A[a]
            a -= 1
        else:
            A[write_index] = B[b]
            b -= 1

        write_index -= 1

내 풀이와 비교하면, 일단 정렬을 사용하지 않아, 시간복잡도가 O(nlogn)에서 O(n)으로 감소시킬 수 있다.

위의 풀이를 설명하자면 다음과 같다.

• 배열 A(num1)의 끝부분부터 차례대로 값이 큰 요소부터 넣는 게 큰 틀
• 따라서, A의 끝부분부터 차례대로, 배열 A와 B의 요소 둘 중 더 큰 값을 넣는다.

사실 요즘 코딩테스트에서 사용하는 메모리가 큰 차이가 있지 않은 이상 중요하지 않은 걸로 알고 있다.

따라서 좀 더 빠른 위의 풀이가 더 좋은 풀이라는 것을 알 수 있다.