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)의 공간 복잡도를 갖는다.
'자료구조와 알고리즘' 카테고리의 다른 글
[DSA][Linked List] 02. Merge Two Sorted Lists (0) | 2025.06.25 |
---|---|
[DSA][Linked List] 01. Reverse Linked List (0) | 2025.06.23 |
[DSA][Binary Search] 06. Time Based Key-Value Store (4) | 2025.06.21 |
[DSA][Binary Search] 05. Search in Rotated Sorted Array (1) | 2025.06.19 |
[DSA][Binary Search] 04. Find Minimum in Rotated Sorted Array (0) | 2025.06.18 |
댓글