[Leet Code] 4. Median of Two Sorted Arrays

https://leetcode.com/problems/median-of-two-sorted-arrays/?envType=problem-list-v2&envId=array&

 

 

문제 설명

크기가 각각 m과 n인 두 개의 정렬된 배열 nums1과 nums2가 주어집니다. 두 정렬된 배열의 중앙값(Median)을 반환하세요.

 

👀 중요

: 전체 실행 시간 복잡도는 O(log(m+n)) 이어야 합니다.

 

⚠️ O(log(m+n)) 의 문제 풀이는 이진 탐색을 이용하여 풀이해야 한다는것을 인지해야 한다! 

 

 

 

 

 

 

 

 

 

 

 

 

---

 

문제 풀이

 

1️⃣ 직관적인 첫번째 풀이 방법 : 배열을 합친 후 정렬하기 

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    // 1. 두 배열을 하나로 합치기
    int[] merged = new int[nums1.length + nums2.length];
    
    // 2. 복사
    System.arraycopy(nums1, 0, merged, 0, nums1.length);
    System.arraycopy(nums2, 0, merged, nums1.length, nums2.length);
    
    // 3. 정렬
    Arrays.sort(merged);
    
    // 4. 중앙값 찾기
    int n = merged.length;
    if (n % 2 == 0) {
        return (merged[n/2 - 1] + merged[n/2]) / 2.0;
    } else {
        return merged[n/2];
    }
}

 

 

 

결과 : 요구하는 O(log(m+n)) 보다 훨씬 느림 

 

시간 복잡도: O(m + n) 또는 O((m+n)log(m+n))

• 배열 합치기: O(m + n)
• 정렬하기: O((m+n)log(m+n))

 

2️⃣ 이진 탐색을 이용한 풀이 방법

Binary Search(이진 탐색)

정렬된 배열에서 특정 값을 찾을 때, 범위를 절반씩 줄여가며 탐색하는 알고리즘

중간 값과 비교해서 왼쪽 또는 오른쪽 범위 중 절반만 탐색하는 방법

정렬이 되어 있어야 크다, 작다를 판단 할 수 있기 때문에 필수적으로 정렬된 배열에서 사용해야한다. 

// ✅ 이진 탐색 가능
int[] sorted = {1, 3, 5, 7, 9, 11, 13};

// ❌ 이진 탐색 불가능
int[] unsorted = {5, 1, 9, 3, 7};

 

 

선형 탐색과 이진 탐색의 차이 

 

선형 탐색 (Linear Search)

 

• 시간 복잡도: O(n)
• 최악의 경우: 배열 끝에 있으면 n번 확인

 

// 처음부터 끝까지 하나씩 확인
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == target) {
        return i;
    }
}

 

 

이진 탐색 

 

• 시간 복잡도: O(log n)
• 최악의 경우: log₂(n)번만 확인

 

// 중간부터 시작해서 절반씩 제거
while (left <= right) {
    int mid = (left + right) / 2;
    if (arr[mid] == target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
}

 

 

 

Binary Search 기본 구조

public int binarySearch(int[] arr, int target) {
    int left = 0;                    // 왼쪽 끝
    int right = arr.length - 1;      // 오른쪽 끝
    
    while (left <= right) {          // 범위가 유효할 때까지
        int mid = (left + right) / 2; // 중간 위치
        
        if (arr[mid] == target) {
            return mid;               // 찾았다!
        }
        else if (arr[mid] < target) {
            left = mid + 1;           // 오른쪽 절반 탐색
        }
        else {
            right = mid - 1;          // 왼쪽 절반 탐색
        }
    }
    
    return -1;  // 못 찾음
}



배열: [1, 3, 5, 7, 9, 11, 13, 15]
찾는 값: 11

1단계:
[1, 3, 5, 7, 9, 11, 13, 15]
 L        M              R
중간값 7 < 11 → 오른쪽으로!

2단계:
            [9, 11, 13, 15]
             L   M       R
중간값 11 == 11 → 찾았다!

 

 

이진 탐색을 이용하여 문제 풀어보기 

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 1. nums1이 더 짧은 배열이 되도록 보장
        // → 이진 탐색 범위를 최소화하기 위함
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        
        int m = nums1.length;
        int n = nums2.length;
        
        // 2. 이진 탐색 초기 설정
        int left = 0;
        int right = m;
        
        // 3. Binary Search 시작!
        while (left <= right) {
            // nums1의 분할 위치
            int partition1 = (left + right) / 2;
            
            // nums2의 분할 위치 (왼쪽 그룹 크기를 맞추기 위해)
            int partition2 = (m + n + 1) / 2 - partition1;
            
            // 4. 분할선 주변의 값들 구하기
            // (경계 처리: 범위를 벗어나면 무한대/무한소 사용)
            int maxLeft1 = (partition1 == 0) ? 
                Integer.MIN_VALUE : nums1[partition1 - 1];
            int minRight1 = (partition1 == m) ? 
                Integer.MAX_VALUE : nums1[partition1];
            
            int maxLeft2 = (partition2 == 0) ? 
                Integer.MIN_VALUE : nums2[partition2 - 1];
            int minRight2 = (partition2 == n) ? 
                Integer.MAX_VALUE : nums2[partition2];
            
            // 5. 올바른 분할인지 확인
            if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
                // 중앙값 찾음! 🎉
                
                // 전체 길이가 짝수인 경우
                if ((m + n) % 2 == 0) {
                    return (Math.max(maxLeft1, maxLeft2) + 
                            Math.min(minRight1, minRight2)) / 2.0;
                }
                // 전체 길이가 홀수인 경우
                else {
                    return Math.max(maxLeft1, maxLeft2);
                }
            }
            // 6. 분할 위치 조정
            else if (maxLeft1 > minRight2) {
                // nums1의 왼쪽 값이 너무 크다 → 왼쪽으로 이동
                right = partition1 - 1;
            }
            else {
                // nums1의 왼쪽 값이 너무 작다 → 오른쪽으로 이동
                left = partition1 + 1;
            }
        }
        
        // 여기까지 오면 안 됨 (문제 조건상 항상 답이 있음)
        return 0.0;
    }
}

 

 

 

참고 

 

시간 복잡도 비교표 

시간 복잡도	이름	예시	속도
O(1)	상수 시간	배열의 첫 번째 원소 접근	항상 같은 시간
O(log n)	로그 시간	이진 탐색	매우 빠름
O(n)	선형 시간	배열 한 번 순회	보통
O(n log n)	-	정렬 (merge sort)	괜찮음
O(n²)	제곱 시간	이중 for문	느림
O(2ⁿ)	지수 시간	모든 부분집합 찾기	매우 느림