본문 바로가기
자료구조와 알고리즘

[DSA][Binary Search] 07. Median of Two Sorted Arrays

by varcode 2025. 6. 22.
반응형

LeetCode 4

 

07. Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n)).

 

 

[질문하기]

- 배열 안의 원소가 중복될 수 있나요?

- Median의 정의를 어떻게 할까요? (짝수일 때와 홀수일 때)

 

 

[아이디어]

-  각각의 배열에 대해 항상 왼쪽에 반개의 원소가 오도록 인덱스를 선택하고, 각 인덱스에 대해 대소 비교를 통해 중앙값인지를 검사하자.

 

 

[풀이 1] Binary Search

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        arrA, arrB = nums1, nums2
        total = len(arrA) + len(arrB)
        half = total // 2

        if len(arrA) > len(arrB):
            arrA, arrB = arrB, arrA
        
        l, r = 0, len(arrA) - 1
        while True:
            mA = l + (r - l) // 2
            mB = half - mA - 2

            leftA = arrA[mA] if mA >= 0 else float("-infinity")
            rightA = arrA[mA + 1] if (mA + 1) < len(arrA) else float("infinity")
            leftB = arrB[mB] if mB >= 0 else float("-infinity")
            rightB = arrB[mB + 1] if (mB + 1) < len(arrB) else float("infinity")
        
            if leftA <= rightB and leftB <= rightA:
                if total % 2:
                    return min(rightA, rightB)
                return (max(leftA, leftB) + min(rightA, rightB)) / 2
            elif leftA > rightB:
                r = mA - 1
            else:
                l = mA + 1

두 배열 nums1, nums2는 정렬되어 있기 때문에, 이들을 정렬된 상태로 합치면 중앙값(median)을 찾는 것은 어렵지 않다. 전체 길이에 따라 홀수이면 가운데 하나, 짝수이면 가운데 두 값의 평균을 구하면 된다. 하지만 배열을 실제로 합치게 되면 시간 복잡도가 O(n + m) 이상으로 늘어나게 된다.

이 문제의 핵심은 배열을 합치지 않고도 중앙값을 찾는 것이고, 각각의 arr에 대해서 계산을 하며 중앙값이 될 인덱스를 찾아야 하는데, 이 인덱스는 다음 두 가지 조건을 만족해야 한다.

1) 왼쪽 파티션에 정확히 half개의 원소가 있어야 한다. half = (len(nums1) + len(nums2)) // 2

2) 왼쪽 파티션의 모든 값 ≤ 오른쪽 파티션의 모든 값이어야 한다. 즉, max(left side) ≤ min(right side)

 

이를 만족하기 위해 한쪽 배열(arrA)에 이진 탐색을 적용한다. mA를 arrA의 왼쪽 파티션 끝 인덱스로 두면 arrA의 왼쪽 파티션 원소 개수는 mA + 1이다. 전체에서 왼쪽 파티션에 half개가 있어야 하므로, 나머지 half - (mA + 1)개는 arrB에서 가져와야 한다. 따라서 arrB의 왼쪽 파티션 끝 인덱스는 mB = half - mA - 2, 즉, mA를 기준으로 mB는 자동으로 결정되며, mA를 적절히 이진 탐색하여  중앙값을 찾는다.

만약 1번 조건을 만족하도록 두 인덱스를 설정했는데, 2번 조건이 맞지 않는다면 인덱스를 재 조정해야 한다.

그림에서처럼 새로운 인덱스들에 대해 그 길이의 합이 half가 되어야 하는 건 고정이다. 따라서 주황색의 왼쪽 구간의 합과 앞선 초록색의 왼쪽 구간의 합은 똑같이 half여야 한다.

 

이렇게 항상 왼쪽에 half개가 오도록 mA, mB가 결정되면, 분할이 정확한지 확인하는 (2번도 만족하는) 조건으로 다음 네 가지 값 leftA, rightA, leftB, rightB를 비교한다.

 

분할이 되었다면?

leftA ≤ rightB and leftB ≤ rightA 조건이 만족되면, 두 배열을 합쳤을 때 정렬된 상태에서 정확히 가운데를 나눈 것이고,
중앙값을 다음 방식으로 계산할 수 있다.

 

  • 총 길이가 홀수 → min(rightA, rightB)
  • 총 길이가 짝수 → (max(leftA, leftB) + min(rightA, rightB)) / 2

 

 

✅ 분할이 안 되었다면?

 

  • leftA > rightB → arrA의 왼쪽 파티션이 너무 큼 → 왼쪽으로 이동 (r = mA - 1)
  • leftB > rightA → arrA의 왼쪽 파티션이 너무 작음 → 오른쪽으로 이동 (l = mA + 1)

 

이런 방법으로 두 배열을 합치지 않고도 중앙값을 구할 수 있다.

 

⏱️ 시간복잡도

각 배열의 길이를 n, m이라 하면 항상 더 짧은 배열에 대해 이진 탐색을 수행하므로 O(log(min(n, m)))의 시간 복잡도를 갖는다.


🧠 공간복잡도

추가 배열을 사용하지 않고 상수 개의 변수만 사용하므로 O(1)의 공간 복잡도를 갖는다.

반응형

댓글