4. Median of Two Sorted Arrays

크기 순으로 정렬 되어 있는 두 개의 배열을 합친 배열의 중간값을 찾는 문제이다.

---

 

배열이 이미 정렬이 각각 되어 있는 상태이기 때문에 각각의 배열을 작은 수부터 비교해나가며 몇번째인지 count 한다면 두 배열을 합쳐서 재정렬시키는 것 보다 연산횟수를 크게 줄일 수 있다고 생각했다.

따라서 3번문제에서처럼 here1과 here2라는 나만의 인덱스를 만들어서 비교해나가는 방식을 택했다.

---

이번에 코드를 짜면서 어려웠던 점과 느낀 점이 몇 가지 있어서 나열해보았다.

 

• '빈 배열'과 같은 예외 처리의 중요성 

      - 인덱스인 here값의 초기값이 0인데 배열이 비어있다면 out of index이기 때문에 예외 처리를 앞서 해주었다.

 

• len값과 index번호의 차이로 인한 while문 조건의 혼란

     - len값은 배열의 길이이기 때문에 0부터 시작하는 배열의 index의 최댓값보다 1이 크다. 이것 때문에 while문의

       조건이 (total + 1) / 2인지 (total - 1)/2인지 혼동되었다.

 

• 총 길이가 짝수인 경우에 두 개의 result값을 저장해야되기 때문에 result2라는 변수를 만들지 않고 프로그래밍하기 위해 노력하였다.

 

• 프로그래밍을 하기 전에 노트에 미리 확실히 구상을 해두는 것이 코딩 중에 방향성을 놓치지 않는데 도움을 준다고 생각한다.

소스코드

 

** 리스트 맨 뒤에 원소 추가를 하는 명령어 : list.append(값)

14. List(리스트)(4) - 리스트 원소 추가, 삭제 - 파이썬 - 기본을 갈고 닦자! (wikidocs.net)

위키독스

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        total = len(nums1) + len(nums2)
        here1 = 0
        here2 = 0
        ind = 0 #밑에 if문에서 ind가 나중에 증가하므로 while문이 ind가 0 ~ 중간번째 수 -1 까지 작동하게 한다.
        result = 0
        nums1.append(1000000) #len 길이 넘어갈 경우를 위해 모든 수보다 큰 값을 끝에 넣어놓는다.
        nums2.append(1000000)
        if len(nums1) == 0: #왼쪽 배열이 크기가 0인 경우 (nums[here1]이 존재하지 않으므로 따로 경우를 만들어줌)
            if len(nums2) % 2 == 1:
                return nums2((len(nums2)-1)/2)
            else :
                return (nums2((len(nums2)/2)) + nums2((len(nums2)/2)-1)) / 2
        elif len(nums2) == 0: #오른쪽 배열의 크기가 0인 경우
            if len(nums1) % 2 == 1:
                return nums1((len(nums1)-1)/2)
            else :
                return (nums1((len(nums1)/2)) + nums1((len(nums1)/2)-1)) / 2
        
        if total % 2 == 1: #총 길이가 홀수인 경우 (중간값 하나만 찾으면 됨)
            while ind != (total + 1) / 2:
                if nums1[here1] <= nums2[here2]:
                    ind += 1
                    result = nums1[here1]
                    here1 += 1
                else:
                    ind += 1
                    result = nums2[here2]
                    here2 += 1
            return result
        else: #총 길이가 짝수인 경우 (중간값 두개 평균 내야함)
            while ind != (total / 2):
                if nums1[here1] <= nums2[here2]:
                    ind += 1
                    result = nums1[here1]
                    here1 += 1
                else:
                    ind += 1
                    result = nums2[here2]
                    here2 += 1
            if nums1[here1] <= nums2[here2]:
                result += nums1[here1]
            else:
                result += nums2[here2]
            return result / 2