💡 문제
median-of-two-sorted-arrays (https://leetcode.com/problems/median-of-two-sorted-arrays/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.
📝 선행 개념
정렬된 두 배열의 중앙값(Median of Two Sorted Arrays) 문제는
“정렬된 두 배열을 병합하지 않고 중앙값을 찾는” 고전적인 이진 탐색 문제입니다.
전체를 합치지 않아도,“왼쪽 파티션의 최대값 ≤ 오른쪽 파티션의 최소값”이 되는 경계 지점만 찾으면 중앙값을 바로 계산
🤓 문제 풀이
두 개의 정렬된 배열 nums1, nums2가 주어질 때,
두 배열을 하나로 합쳤을 때의 중앙값(median)을 구하라.
단, 전체를 병합하지 않고 O(log(m+n)) 시간 복잡도 내에 해결해야 한다.
🔨 문제 설명
정렬된 두 배열을 “병합 없이” 가운데에서 자르는 법을 찾는 문제
- “Given two sorted arrays …” (두 배열은 이미 정렬됨)
- 정렬 특성 덕에 양쪽에서 일부만 보더라도 어느 쪽이 더 작은지 판단 가능.
- 전략: 전체를 합치지 않고, 경계(파티션)만 올바르게 잡으면 중앙(중앙값)을 바로 계산할 수 있음.
- “The overall run time complexity should be O(log (m+n))”
- 단순 병합(두 포인터)은 O(m+n) → 불합격.
- 전략: 이진 탐색으로 파티션 위치를 찾는 접근이 필요.
- 일반적으로 더 짧은 배열을 기준으로 파티션 위치를 이진 탐색하면 O(log min(m, n)) ⊆ O(log(m+n)).
- 출력: ‘median’(중앙값)
- 중앙값 정의상, 왼쪽 파티션의 최대값 ≤ 오른쪽 파티션의 최소값이 되는 지점이 정답.
- 합계 길이가 홀수면 왼쪽 파티션 최대값이 중앙값, 짝수면 왼쪽 최대와 오른쪽 최소의 평균.
🔨 접근 방법
1) 파티션 정의
- i = nums1에서 왼쪽에 둘 원소 개수, j = nums2에서 왼쪽에 둘 원소 개수.
- 전체 길이 T = m + n. 왼쪽 파티션 총 원소 수는 L = (T + 1) / 2 (홀/짝 공통 처리):
- 그래서 j = L - i 로 자동 결정.
- 목표:이 불변식이 성립하면 올바른 중앙 경계에 도달.
- max( nums1[i-1], nums2[j-1] ) <= min( nums1[i], nums2[j] )
2) 이진 탐색 범위
- 짧은 쪽(예: nums1)에서 i를 [0, m] 범위로 이진 탐색.
- 각 단계에서 i를 정하면 j = L - i가 정해지므로, 비교는 네 값만 보면 됨:
- Aleft = (i > 0 ? nums1[i-1] : -∞)
- Aright = (i < m ? nums1[i] : +∞)
- Bleft = (j > 0 ? nums2[j-1] : -∞)
- Bright = (j < n ? nums2[j] : +∞)
3) 이동 규칙 (불변식 성립까지 조정)
- 만약 Aleft > Bright 라면 ⇒ nums1의 왼쪽이 너무 큼 ⇒ i를 줄인다(high = i - 1).
- 만약 Bleft > Aright 라면 ⇒ nums1의 왼쪽이 너무 작음 ⇒ i를 늘린다(low = i + 1).
- 둘 다 아니라면 불변식 만족 → 정답 계산.
4) 중앙값 계산
- 전체 길이 T = m + n
- 홀수 → median = max(Aleft, Bleft)
- 짝수 → median = (max(Aleft, Bleft) + min(Aright, Bright)) / 2.0
🔨 문제 풀이 과정
- L = (T+1)/2로 왼쪽 파티션의 크기를 고정하면, 왼쪽에 정확히 절반(또는 절반+1)이 위치.
- 이때 왼쪽 최대 ≤ 오른쪽 최소만 만족하면, 왼쪽은 모두 오른쪽보다 작거나 같아 정렬된 전체의 중앙 경계가 됨.
- 정렬된 두 배열의 성질로 인해 i를 하나씩 조정하면 불변식에 수렴. 이 과정이 이진 탐색이므로 로그 시간.
🔨 구현코드
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// (1) 항상 더 짧은 배열을 기준으로 이진 탐색 (시간복잡도 최소화)
if (nums1.length > nums2.length) return findMedianSortedArrays(nums2, nums1);
int m = nums1.length, n = nums2.length;
int total = m + n;
int leftSize = (total + 1) / 2; // 왼쪽 파티션에 들어갈 전체 원소 개수(홀/짝 공통 처리)
int lo = 0, hi = m; // nums1에서 자를 위치 i의 탐색 구간 [0, m]
while (lo <= hi) {
int i = (lo + hi) >>> 1; // nums1의 파티션 위치(i): 중간값 (부호 없는 우시프트로 안전 계산)
int j = leftSize - i; // nums2의 파티션 위치(j)는 i로부터 자동 결정
// (2) 파티션 경계 4개 값 계산 (경계 밖은 ±무한대로 가드해 비교 단순화)
int Aleft = (i > 0) ? nums1[i - 1] : Integer.MIN_VALUE;
int Aright = (i < m) ? nums1[i] : Integer.MAX_VALUE;
int Bleft = (j > 0) ? nums2[j - 1] : Integer.MIN_VALUE;
int Bright = (j < n) ? nums2[j] : Integer.MAX_VALUE;
// (3) 올바른 파티션인지 확인: 왼쪽 최대 ≤ 오른쪽 최소
if (Aleft <= Bright && Bleft <= Aright) {
// 전체 길이 홀수: 왼쪽 최대가 중앙값
if ((total & 1) == 1) {
return Math.max(Aleft, Bleft);
} else {
// 전체 길이 짝수: (왼쪽 최대 + 오른쪽 최소) / 2
int leftMax = Math.max(Aleft, Bleft);
int rightMin = Math.min(Aright, Bright);
return (leftMax + rightMin) / 2.0;
}
}
// (4) 파티션 조정 규칙
// nums1의 왼쪽이 너무 크면 i를 왼쪽으로 당김
if (Aleft > Bright) {
hi = i - 1;
} else {
// nums1의 왼쪽이 너무 작으면 i를 오른쪽으로 밀어 올림
lo = i + 1;
}
}
return 0.0;
}
}📚 풀이 보완
병합하지 않고, 이진 탐색으로 파티션 경계를 찾음
조건 불변식 : max(Aleft, Bleft) ≤ min(Aright, Bright)
코드 설명
- nums1을 항상 짧은 배열로 강제하여 경계 계산 단순화.
- i와 j를 통해 두 배열의 “왼쪽”과 “오른쪽” 영역 크기를 항상 (T+1)/2로 맞춤.
- “왼쪽 최대 ≤ 오른쪽 최소” 불변식이 성립하는 순간이 중앙 경계.
- 두 배열이 이미 정렬되어 있으므로, 일부 구간만 봐도 어느 쪽이 작은지 판단 가능.
- 단순 병합은 O(m+n) → 불합격.
- 이진 탐색(Binary Search) 으로 경계(Partition) 를 올바르게 찾는 방식으로 최적화.
- 항상 더 짧은 배열에서 파티션 위치 i를 탐색하고, 나머지 배열에서의 파티션 j는 (m+n+1)/2 - i 로 자동 결정.
예제로 검증 (예제 2: [1,2], [3,4])
- T=4, L=(4+1)/2=2
- nums1 기준 i를 이진 탐색.
- i=1 → j=1
- Aleft=1, Aright=2, Bleft=3, Bright=4
- Bleft(3) > Aright(2) ⇒ i 늘림
- i=2 → j=0
- Aleft=2, Aright=+∞, Bleft=-∞, Bright=3
- 불변식 성립(2 ≤ 3)
- i=1 → j=1
- 짝수 길이 → median = (max(2, -∞) + min(+∞, 3))/2 = (2+3)/2=2.5 ✔
엣지/코너 케이스
- 한 배열이 비었을 때: 이식(±∞ 처리)으로 자연스럽게 해결.
- 중복/음수/큰 수 범위: 비교만 하므로 특이 처리 불필요.
- 매우 길이 차이 큼: 짧은 배열에서만 이진 탐색하므로 안정적.
- 실수 반환 형식: 짝수 합일 때 정확히 평균 계산(정수 나눗셈 주의).
📍 Plus+
시간 복잡도와 공간 복잡도 분석
- 시간: O(log min(m, n))
- 공간: O(1) (상수 변수만 사용)
시간 복잡도
- 짧은 배열 기준 이진 탐색 → O(log min(m, n))
공간 복잡도
- 상수 변수만 사용 → O(1)
실수했던거
- 병합해서 중앙값(O(m+n)) → 시간 초과 의도
- L = (T+1)/2로 설정하지 않아 홀수 케이스 삐끗
- 경계 인덱스에서 ±∞ 가드 누락
- i 변화 방향을 조건과 반대로 적용
- 짝수 케이스에서 정수/실수 평균 처리 실수
시간복잡도: O(log min(m, n)), 추가공간: O(1).