4. Median of Two Sorted Arrays
GPT
좋아요! 다시 처음부터 차근차근, 이 문제를 해결하기 위해 "왼쪽 부분의 최대값 ≤ 오른쪽 부분의 최소값" 조건이 필요한 이유와 이 조건을 중심으로 문제를 푸는 방식을 전체적으로 설명하겠습니다.
문제의 목표
- 두 개의 정렬된 배열 nums1과 nums2가 주어집니다.
- 이 두 배열을 병합한 후 **중앙값(중간값, Median)**을 구해야 합니다.
- 단, 병합하지 않고 O(log(m + n)) 시간 복잡도 안에 해결해야 합니다.
중앙값(Median)의 정의
중앙값은 정렬된 배열에서 중앙에 위치한 값입니다. 배열의 길이에 따라 정의가 달라집니다.
- 배열의 길이가 홀수인 경우:
- 중앙에 위치한 하나의 값이 중앙값.
- 예: [1, 3, 5] → 중앙값은 3.
- 배열의 길이가 짝수인 경우:
- 중앙에 위치한 두 값의 평균이 중앙값.
- 예: [1, 3, 5, 7] → 중앙값은 (3 + 5) / 2 = 4.
문제의 핵심
배열을 병합하지 않고도 중앙값을 구하는 방법을 찾아야 합니다.
병합하지 않고 중앙값을 구하려면?
- 병합된 배열의 왼쪽 부분과 오른쪽 부분을 나눌 수 있어야 합니다.
- 이 두 부분은 다음 조건을 만족해야 합니다:
- 왼쪽 부분의 모든 값 ≤ 오른쪽 부분의 모든 값.
- 이 조건이 성립하면, 두 부분의 경계에 중앙값이 위치합니다.
병합된 배열을 나누는 예시
예를 들어, 배열 nums1 = [1, 3], nums2 = [2, 4]가 있다고 합시다.
- 병합된 배열: [1, 2, 3, 4].
- 왼쪽 부분: [1, 2].
- 오른쪽 부분: [3, 4].
이때:
- 왼쪽 부분의 최대값 = 2.
- 오른쪽 부분의 최소값 = 3.
- 조건 2 ≤ 3이 성립합니다.
- 중앙값 = (2 + 3) / 2 = 2.5.
병합 없이 중앙값 찾기: 이진 탐색 활용
두 배열을 병합하지 않고 이진 탐색을 통해 중앙값을 찾습니다. 핵심은 두 배열을 적절히 나누는 위치를 찾는 것입니다.
이진 탐색을 사용하는 이유
- O(log(m + n)) 시간 복잡도를 만족하기 위해 이진 탐색을 사용합니다.
- 두 배열 중 하나(길이가 더 짧은 배열)에 대해 탐색 범위를 좁혀 나갑니다.
- 나눔 기준을 적절히 찾으면 병합된 배열의 중앙값을 직접 계산할 수 있습니다.
나눔 기준: 왼쪽과 오른쪽 부분의 조건
두 배열을 각각 왼쪽과 오른쪽 부분으로 나누어 다음 조건을 만족시켜야 합니다:
- 왼쪽 부분의 최대값 ≤ 오른쪽 부분의 최소값.
이 조건의 의미
- 왼쪽 부분의 최대값:
- 나뉜 두 배열의 왼쪽 부분에서 가장 큰 값.
- 오른쪽 부분의 최소값:
- 나뉜 두 배열의 오른쪽 부분에서 가장 작은 값.
- 조건이 성립한다면:
- 병합된 배열이 적절히 나누어졌고, 중앙값을 계산할 수 있습니다.
조건이 성립하지 않는 경우
- 왼쪽 부분의 최대값 > 오른쪽 부분의 최소값:
- 나눔이 잘못되었습니다.
- 이 경우 탐색 범위를 조정합니다:
- 왼쪽 값이 너무 크면 더 왼쪽으로 이동 (r = mid1 - 1).
- 오른쪽 값이 너무 작으면 더 오른쪽으로 이동 (l = mid1 + 1).
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
# 항상 nums1이 짧은 배열이 되도록 설정
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
total_len = m + n
half_len = total_len // 2
l, r = 0, m
while l <= r:
mid1 = (l + r) // 2
mid2 = half_len - mid1 # 두 배열을 나누는 기준
left1 = nums1[mid1 - 1] if mid1 > 0 else float('-inf')
right1 = nums1[mid1] if mid1 < m else float('inf')
left2 = nums2[mid2 - 1] if mid2 > 0 else float('-inf')
right2 = nums2[mid2] if mid2 < n else float('inf')
# 조건 확인
if left1 <= right2 and left2 <= right1:
# 조건을 만족하면 중앙값 계산
if total_len % 2 == 0:
return (max(left1, left2) + min(right1, right2)) / 2
else:
return min(right1, right2)
# 조건을 만족하지 않으면 탐색 범위 조정
elif left1 > right2:
r = mid1 - 1
else:
l = mid1 + 1
요약
- 두 배열을 병합하지 않고도 중앙값을 찾기 위해 두 배열을 나누는 기준을 찾습니다.
- 이 기준은 왼쪽 부분의 최대값 ≤ 오른쪽 부분의 최소값이라는 조건으로 표현됩니다.
- 조건이 성립하지 않으면 이진 탐색을 통해 나눔 기준을 조정합니다.
- 조건이 성립하면 중앙값을 계산합니다:
- 홀수: 오른쪽 부분의 첫 번째 값.
- 짝수: 왼쪽 부분의 최대값과 오른쪽 부분의 최소값의 평균.
https://youtu.be/q6IEA26hvXc?si=hRCnN8N1wU1nk9Rb
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
A, B = nums1, nums2
total = len(nums1) + len(nums2)
half = total // 2
if len(B) < len(A): # len(A) < len(B) 이 되게..
# Ensure that A is always the smaller array for efficient binary search
A, B = B, A
l, r = 0, len(A) - 1
while True:
i = (l + r) // 2 # A
"""
# i최대값+1 = len(nums1), j최대값+1 = len(nums2)
# total = len(nums1) + len(nums2)
# half = total // 2 이므로.
# i, j 가 각 A, B 의 중간값이므로,
# (i+1) + (j+1) = half 가 되어야 함
# 따라서, j = half - i - 2 수식이.. 자동으로..
# i+1 represents the number of elements in the left half of A.
# j+1 represents the number of elements in the left half of B.
# The total elements in the left half of both arrays = `half`.
# Therefore, j = half - i - 2 ensures proper partitioning.
"""
j = half - i - 2 # B, -2는 배열 index 가 0부터 시작하므로,
"""
# A[i], B[j] 는 A와 B의 작은쪽의 최대값
# A[i+1], B[j+1] 는 A와 B의 큰쪽의 최소값
# 따라서, i,j 와 i+1, j+1이 유효 범위에 없으면
# A[i], B[j] 는 A와 B의 작은쪽의 최대값, 즉, 음수 무한대를 가져야 함
# A[i+1], B[j+1] 는 A와 B의 큰쪽의 최소값, 즉 양수 무한대 가져야 함
# A[i], B[j] represent the maximum of the smaller side of A and B.
# A[i+1], B[j+1] represent the minimum of the larger side of A and B.
# If i or j go out of bounds, we use negative infinity (for max)
# or positive infinity (for min) as a fallback.
"""
Aleft = A[i] if i >= 0 else float("-inf") # A의 왼쪽 절반의 최대값 (없으면 -∞)
Aright = A[i + 1] if i + 1 < len(A) else float("inf") # A의 오른쪽 절반의 최소값 (없으면 ∞)
Bleft = B[j] if j >= 0 else float("-inf") # B의 왼쪽 절반의 최대값 (없으면 -∞)
Bright = B[j + 1] if j + 1 < len(B) else float("inf") # B의 오른쪽 절반의 최소값 (없으면 ∞)
# partition is correct
if Aleft <= Bright and Bleft <= Aright:
"""
# odd 홀수
# 전체 길이가 홀수인 경우, 오른쪽 절반의 최소값이 중앙값이 됨
# If the total length is odd, the median is the minimum value
# of the right halves.
"""
if total % 2:
return min(Aright, Bright)
"""
# even 짝수
# 전체 길이가 짝수인 경우, 왼쪽 절반의 최대값과 오른쪽 절반의 최소값의 평균이 중앙값
# If the total length is even, the median is the average of the
# maximum value of the left halves and the minimum value of the right halves.
"""
return (max(Aleft, Bleft) + min(Aright, Bright)) / 2
elif Aleft > Bright:
"""
# A의 작은쪽의 최대값 < B의 큰쪽의 최소값 여야 하는데,
# 반대 상황이니
# i 를 줄여야 하는 상황
# If A's left maximum is greater than B's right minimum,
# i needs to move left, reducing the range.
"""
r = i - 1
else:
"""
# j를 줄여야 하는데, j=half-i 이므로, i를 늘려야 하는 상황
# If B's left maximum is greater than A's right minimum,
# i needs to move right, increasing the range.
"""
l = i + 1'LeetCode > 주제별 보충' 카테고리의 다른 글
| Graphs: 127. Word Ladder ★★★★★ (0) | 2024.12.23 |
|---|---|
| Heap-PrioiryQueue: 295. Find Median from Data Stream ★★★ (0) | 2024.12.22 |
| Bit: 191. Number of 1 Bits (0) | 2024.12.17 |
| Bits: 190. Reverse Bits (0) | 2024.12.17 |
| Graphs(싸이클탐지): 207. Course Schedule ★★★ (0) | 2024.12.16 |