[LeetCode/Java] Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/

[문제 설명]

두개의 정렬된 배열(nums1, nums2)이 주어졌을 때, 두 배열의 중앙값 찾기

단, 시간 복잡도는 O(log(m+n)) * m : nums1의 길이, n : nums2의 길이

 

[주의사항]

중앙값을 찾아야하네? -> 두 배열을 합쳐서 정렬한 뒤 중앙값을 찾자 (XXXXXXX)

배열을 합치고 정렬하는 방식의 시간 복잡도는 O((m+n) log(m+n))이기 때문에 문제의 조건과 어긋남

 

[접근 방법]

1. 병합하지 않는다

 

2. 짧은 배열에 대해 이진 탐색(Binary Search)을 수행한다

짧은 배열에 대해 이진 탐색을 하는 이유는 탐색 범위를 줄여서

시간 복잡도를 O(log(min(m,n))로 제한하기 위함

 

3. 배열 분할하기

두 배열을 왼쪽 파티션과 오른쪽 파티션으로 나누는데,

왼쪽 파티션에 전체 원소의 절반(또는 절반보다 1개가 더 많은 경우)이 오도록 함

 

분할점 설정

x : nums1의 길이, y : nums2의 길이

partitionX	nums1의 분할점
partitionY	nums2의 분할점	(x + y + 1) / 2 - partitionX

 

4. 경계값 설정 및 비교

설명	nums1	nums2
분할점 왼쪽의 가장 큰 값 만약 분할점이 0이면, 왼쪽에 원소가 없으므로 Integer.MIN_VALUE	maxLeftX	maxLeftY
분할점 오른쪽의 가장 작은 값 만약 분할점이 배열의 길이와 같다면, 오른쪽에 원소가 없으므로 Integer.MAX_VALUE	minRightX	minRightY

 

5. 분할 조건

• maxLeftX <= minRightY
• maxLeftY <= minRightX

=> 만족하면, 왼쪽 파티션에 전체 원소의 절반 이상이 들어간 것

 

6. 중앙값 계산하기

• 전체 원소 수가 짝수인 경우
  max(maxLeftX, maxLeftY) + min(minRightX, minRightY) / 2
• 전체 원소 수가 홀수인 경우
  max(maxLeftX, maxLeftY)

 

7. 이진 탐색 범위 조정

• maxLeftX > minRightY
  nums1에서 너무 많은 원소가 왼쪽 파티션에 포함된 것이므로, 분할점을 왼쪽으로 이동
• maxLeftY > minRightY
  분할점을 오른쪽으로 이동

 

[문제 풀이]

package leetcode;

public class TwoSortedArrays {

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // nums1이 항상 더 짧은 배열이 되도록 스왑
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int x = nums1.length;
        int y = nums2.length;
        
        int low = 0;
        int high = x;
        
        while (low <= high) {
            // nums1의 중간 위치를 기준으로 분할점 설정
            int partitionX = (low + high) / 2;
            // 전체 원소의 절반이 왼쪽 파티션에 오도록 nums2에서의 분할점 결정
            int partitionY = (x + y + 1) / 2 - partitionX;
            
            // 분할점의 경계값 처리 (배열의 시작이나 끝일 경우)
            int maxLeftX = (partitionX == 0) ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int minRightX = (partitionX == x) ? Integer.MAX_VALUE : nums1[partitionX];
            
            int maxLeftY = (partitionY == 0) ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int minRightY = (partitionY == y) ? Integer.MAX_VALUE : nums2[partitionY];
            
            // 올바른 분할 조건 확인
            if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
                // 전체 원소 수가 짝수인 경우
                if ((x + y) % 2 == 0) {
                    return ((double) Math.max(maxLeftX, maxLeftY) + Math.min(minRightX, minRightY)) / 2;
                } else {
                    // 홀수인 경우 왼쪽 파티션의 최대값이 중앙값
                    return (double) Math.max(maxLeftX, maxLeftY);
                }
            } else if (maxLeftX > minRightY) {
                // nums1에서 너무 많은 원소가 왼쪽에 포함된 경우 -> 분할점을 왼쪽으로 이동
                high = partitionX - 1;
            } else {
                // 그렇지 않다면 분할점을 오른쪽으로 이동
                low = partitionX + 1;
            }
        }
        
        return -1;
    }
    
    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        
        double median = findMedianSortedArrays(nums1, nums2);
        System.out.println("중앙값: " + median); // 예제 출력: 중앙값: 2.0
    }
}

[풀이 해설]

1. 짧은 배열 <-> 긴 배열 바꿔주기

if (nums1.length > nums2.length) 조건을 통해 항상 nums1이 짧은 배열이 되도록 스왑

 

2. 이진 탐색을 위한 초기 설명

low와 high를 nums1길이에 맞춰 초기화

 

3. 이진 탐색 및 분할점 설정

while루프 내에서 partitionX를 이진 탐색으로 찾고, 이에 따라 partitionY를 계산

 

4. 경계값 계산

분할점에 따른 maxLeftX, minRightX, maxLeftY, minRightY 값을 설정

 

5. 분할 확인

maxLeft <= minRightY && maxLeftY <= minRightX 만족하면, 전체 원소 수의 홀수/짝수 여부에 따라 중앙값 계산

 

6. 최종

while루프 내에서 올바른 분할을 찾게 되면 즉시 중앙값 반환