⭐️ LeetCode 알고리즘 풀이 (with Python)

# Median of Two Sorted Arrays

[Quetion]

LeetCode 4. Median of Two Sorted Arrays

📌 접근법

[문제 이해]

• 두 리스트를 합쳤을 때 오름차순 정렬한 상태에서의 중앙값 반환
• O(log m+n)의 시간복잡도 제한

문제에서 요구한 대로 우선 두 리스트를 더하고, 병합정렬(O nlogn)기반의 sorted() 함수로 정렬하는 방법을 생각했다.

정렬한 리스트의 길이가 홀수일 경우 중앙값을 그대로 반환하고, 짝수이면 중앙값 2개의 평균을 계산하도록 했다.

💻 구현

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums=sorted(nums1+nums2)
        mid=len(nums)//2
        if len(nums)%2!=0:
            return nums[mid]
        else:
            return (nums[mid] + nums[mid-1])/2

Runtime: 81ms | Memory: 16.4MB
LeetCode 코드 중 Runtime 93%, Memory 84% 해당하는 결과

📌 로직 핵심

• 병합정렬 기반의 sorted()함수로 오름차순 정렬

📝 Median of Two Sorted Arrays 회고

• 시간복잡도는 정렬과정에서 발생한 O(n log n)이고 공간복잡도는 O(1)이다.
• 난이도 Hard 문제였지만 내장 함수의 시간복잡도를 잘 알고 활용한다면 쉽게 접근이 가능한 문제였다.
• two pointer 방법과 분할정복의 개념으로 접근할 수도 있으나, 성능 차이는 거의 없다고 판단했고, 오히려 포인터 변수를 많이 할당하게 되어 메모리를 더 사용하며 코드 복잡도도 증가할 거라 생각했다.