[Binary Search][Hard] 4. Median of Two Sorted Arrays

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

 

 

Q. 주어진 정렬된 array nums1과 nums2가 주어질 때, 두 array를 정렬하여 합친 array의 median 값을 구하라. 

 이때 TC가 O(log(m+n)) 이 되도록 하라. 

 

 

 

Solution. 

 우선 median 값의 정의부터 알 필요가 있겠다. 

 어떤 array의 가운데 위치의 값을 뜻하는데, 길이가 홀수이면 그 중앙 값을 취하면 되겠지만, 

 짝수일 때는, 인접한 중앙값 두 개의 평균을 구하면 되는 것이다. 

 즉, index상 중앙에 위치한 값들에 의해 결과가 정해진다. 

 

 우선 간단하게 두 정렬된 array들을 merge sort 해 본다. 

 이후 중앙 값을 median 값을 취하는 로직대로 취한다. 

 

 

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
{
    vector<int> vRet;
    int idx1 = 0, idx2 = 0;
    for (int k = 0; k < nums1.size() + nums2.size(); ++k)
    {
        if (idx1 >= nums1.size() || idx2 >= nums2.size())
        {
            if (idx1 >= nums1.size())
                vRet.push_back(nums2[idx2++]);
            else
                vRet.push_back(nums1[idx1++]);
        }
        else
        {
            if (nums1[idx1] < nums2[idx2])
                vRet.push_back(nums1[idx1++]);
            else
                vRet.push_back(nums2[idx2++]);
        }
    }
    int mid = vRet.size() / 2;
    if (vRet.size()%2==1)
        return vRet[mid];
    else
       return ( ((double)(vRet[mid - 1] + vRet[mid])) / 2.0);
}

 결과

 

비교적 간단하게 구할 수 있지만, 

 이 방식은 O(m+n)의 TC가 요구된다. 

 따라서 문제가 원하는 해결 방식은 아닌 것이다. 

 

 

 

 

문제가 요구하는 TC는 O(log(m+n))로, 주어진 배열 또한 정렬되어 주어진다. 

간단하게 말해서, binary search를 쓰라는 것이다.

 

 즉 중요한 것은,  

 두 개의 주어진 array에 대해........

 나머지 반을 취하고 반대 반을 버릴 진행 요건,

 만족/중지 요건, 

 그리고 관련 예외처리 정도 되겠다. 

 

 우선 어떤 요건 일 때 만족/중지 될까. 즉, median 값이 될까. 

 이 전에 우리는 먼저 num1과 num2의 분할이 각각 독립적이지 않다는 사실을 알아야 할 필요가 있다. 

 예를 들어 num1 수가 3이고 num2의 수가 5라면, 

 num1을 A | B, C 로 분할 한다면, num2는 X X X | O O 로 분할이 될 것이다. 

 왜냐하면, 우리는 물리적으로 가운데의 위치를 찾으려 하고 있으므로, 파티션의 좌변 우변의 수가 같은 경우가 그렇기 때문이다. 

 num1의 파티션 위치가 A B | C 일때는, num2 는 X X | O O O 식이 될 것이다. 

 따라서 이를 수식화 할 수 있고, 

 이를 이용해 한 배열에 대해서만 파티션 로직을 분할 진행 하면, 나머지 배열은 그에 종속됨을 알았다. 

 

  또한, 우리는 정렬된 배열을 사용하므로, 

  파티션 된 좌변이 파티션 된 우변보다 작아야 median을 만족 함을 알 수 있다. 

  즉, num1의 A1 A2 | A3 , num2의  B1 B2 | B3 B4 B5 로 분할 시

   max(A2, B2) < min(A3, B3) 이어야 함을 알 수 있다. 

   num1, num2는 각각 정렬된 상태이므로, 더 정확히는 

   A2<B3 && B2<A3 이어야만, median을 만족하는 상태가 되겠다. 

     => 이때는 올바른 상태이므로 median 값을 반환한다.

   A2>B3 인 상태이면, 이미 num1이 num2에 비해 큰쪽에 파티션이 위치하고 있다는 의미이므로, 우측을 버리고 좌측을 택한다. 

   B2>A3 인 상태면, num1이 너무 작다는 의미이므로, 큰 쪽인 우측을 취할 필요가 있다. 

     

  마지막으로, 어떤 배열을 먼저 파티션하고, 다음 배열을 이에 종속시켜 정할까. 

  길이가 작은 배열을 num1으로 파티션하는 것이 유리한데, 그 이유는 길이가 긴 편에서는 치우친 값이 더 많기 때문에 비 효율적이게 되기 때문에 그렇다. 

  

 

   정리한 내용을 코드로 풀어본다. 

 

double median_bs(vector<int>& nums1, vector<int>& nums2, int left, int right)
{
    // num1의 파티션을 먼저 구하고 그에 의해 partition2의 위치를 정한다.
    int num1Partition = left>=right ? left : 1 + (left + (right - left) / 2);
    int num2Partition = (nums1.size() + nums2.size()) / 2 - num1Partition;

    // 파티션의 좌우 index의 값을 비교 값으로 취한다.
    int idxNum1L = num1Partition - 1;
    int idxNum1R = num1Partition;
    int idxNum2L = num2Partition - 1;
    int idxNum2R = num2Partition;

    // 범위를 벗어나면, 비교에서 항상 배제되도록 INT_MIN, INT_MAX를 set 한다.
    int N1Left  = idxNum1L >= 0 && idxNum1L < nums1.size() ? nums1[idxNum1L] : INT_MIN;
    int N1Right = idxNum1R >= 0 && idxNum1R < nums1.size() ? nums1[idxNum1R] : INT_MAX;
    int N2Left  = idxNum2L >= 0 && idxNum2L < nums2.size() ? nums2[idxNum2L] : INT_MIN;
    int N2Right = idxNum2R >= 0 && idxNum2R < nums2.size() ? nums2[idxNum2R] : INT_MAX;

    // 모든 좌항이 우항보다 작으면 median을 만족한다.
    if (N1Left <= N2Right && N2Left <= N1Right)
    {
        // 배열 길이에 따라 결과를 구한다.
        if ((nums1.size() + nums2.size()) % 2 == 0)
            return (max(N1Left, N2Left) + min(N1Right, N2Right)) / 2.0;
        else
            return min(N1Right, N2Right);
    }
    // N1이 너무 크다. 왼쪽을 취한다.
    else if (N1Left > N2Right)
        return median_bs(nums1, nums2, left, num1Partition - 1);

    // N2가 너무 작다. 오른쪽을 취한다.
    else
        return median_bs(nums1, nums2, num1Partition+1, right);
}

double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
    // 첫째 파티션이 항상 작은 길이의 배열에서 생기도록 한다.
    if(nums1.size() < nums2.size())
        return median_bs(nums1, nums2, 0, nums1.size() - 1);
    else 
        return median_bs(nums2, nums1, 0, nums2.size() - 1);
}

 

최적화가 더 필요해 보이긴 하지만, 아무튼, 결과를 얻었다. (병합정렬보다 더 느린건 무엇.....)

 

 

Note) 이 문제는 쉽지 않다. 많은 이해를 기반으로 한 전제들을 확인해야 하고, 비교적 완벽한 예외처리를 해야 오류 없이 문제가 풀린다. 

 Leetcode의 대부분의 문제는 직관보다는 훈련에 의해 풀이 능력을 향상시킬 수 있다고 믿는다. 

 이 문제로 그런 대표적인 문제중의 하나다. 다시말해 직관으로 풀기는 거의 불가능에 가깝다. 

 

 비슷한 예제를 다양한 방법으로 풀어보는 것이 당연하겠지만, 가장 효율적인 공부법이 될 것이다.