[Python/LeetCode]코딩테스트 준비를 위한 파이썬 알고리즘 문제 4.Median of Two Sorted Arrays 해설(High level)

문제 4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
You may assume nums1 and nums2 cannot be both empty.
Example 1:
nums1 = [1, 3] nums2 = [2] The median is 2.0
Example 2:
nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5

두 개의 sorted list가 존재하며 두 list는 비어있지 않는 경우에 중간값을 찾으면 됩니다.

 

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        #nums1 과 nums2 합치기
        nums1.extend(nums2)
        #합쳐진 list 정렬
        nums1.sort()
        #홀짝을 알기 위해 몫과 나머지를 구함
        quotient = len(nums1) // 2
        remainder = len(nums1) % 2
        
      	#나머지가 0이 아니면 홀수이므로 몫의 위치(중간값)을 그대로 가져오고 아닌 경우 몫 +-1의 값을 가져옴
        if remainder == 0 :
            
            median = float((nums1[quotient-1]+nums1[quotient]))/2
            
        else:
            median = float(nums1[quotient])
            
        return median
            

 

 

python에서 나누기 연산시 아래와 같은 규칙이 있음을 알면 쉬운 문제였습니다. 

float(a/b) : 몫과 나머지 모두
a//b : 몫만
a%b : 나머지만(이때 소수점 이하의 단위로 나오는게 아닌 나머지의 값만 나옵니다.)

 

이 외에도 divmod를 사용하는 방법도 있습니다. 다만 divmod의 경우 연산 숫자가 매우 크고 나머지의 길이가 매우 길거나 절대 나누어 떨어지지 않는 경우에는 빠른 속도를 보이지만 그렇지 않은 대부분의 경우에선 연산자를 통한 연산이 더 빠른 결과를 나타내기 때문에 divmod를 사용하지 않았습니다.