Median of Two Sorted Arrays

문제 링크: https://leetcode.com/problems/median-of-two-sorted-arrays/

1. 문제 파악

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

배열 길이가 각각 m과 n인 배열이 주어졌을 때 두 배열을 합치고, 정렬하여 중앙값을 리턴하라는 것이다.

1-1. 조건

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

첫 번째 배열의 길이는 m이고 두 번째 배열의 길이는 n이다. m과 n은 0 이상 1000 이하이다. m과 n의 합은 1 이상 2000 이하이다. 각 배열의 인덱스 값은 -106 이상 106 이하이다.

1-2. 예제

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Example 3:

Input: nums1 = [0,0], nums2 = [0,0]
Output: 0.00000

Example 4:

Input: nums1 = [], nums2 = [1]
Output: 1.00000

Example 5:

Input: nums1 = [2], nums2 = []
Output: 2.00000

2. 풀이

먼저, 나의 풀이를 살펴보겠다.

2-1. 나의 풀이

먼저 나의 첫 번째 해결 방법이다.

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = nums1 + nums2
        nums.sort()
        i, j = divmod(len(nums), 2)
        
        if j == 0:
            return (float(nums[i-1]) + float(nums[i])) / 2
        else:
            return nums[i]

첫 번째는 함수 인자로 받은 배열 nums1과 nums2를 합치고 정렬을 한 뒤, divmod를 사용하여 i와 j에 각각 2로 나눈 몫과 나머지를 넣어준다.

나머지가 0일 경우 Example 2와 같이 사이 값을 줘야하므로 i-1번째와 i번째 인덱스 값을 더하고 2로 나눈 값을 리턴해준다. 반대로 나머지가 1인 경우 i번째 인덱스를 리턴해준다.

다음으로 나의 두 번째 해결 방법이다.

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        nums = nums1 + nums2
        nums.sort()
        i = len(nums) / 2
        
        if len(nums) % 2 == 0:
            return (float(nums[i-1]) + float(nums[i])) / 2
        else:
            return nums[i]

첫 번째 풀이와의 차이점은 divmod를 사용하지 않고 i에 nums 배열의 길이를 2로 나눈 몫만 넣어준 뒤, nums 배열의 길이가 2의 배수일 경우와 배수가 아닐 경우로 나누어 계산했다.

첫 번째에 비해 메모리와 속도 측면에서 조금 발전하였다.