요약

링크 : https://leetcode.com/problems/median-of-two-sorted-arrays/description/
결과 : 아이디어를 떠올리지 못한 채 포기했고, 아이디어를 참고 후 통과했습니다.

평가 : 아이디어 자체가 굉장히 어렵고 직관적이지도 않습니다. 풀이를 본 이후로도 소화하는데까지 굉장히 오랜 시간이 걸렸습니다.

설명

문제 자체는 simple합니다. 정렬된 두 배열이 주어질 때, 두 배열의 원소들 중 가운데 있는 값을 찾는 문제입니다.

그런데 시간복잡도가 O(log(두 배열의 크기의 합)) 입니다.
한시간이 넘게 고민을 했는데 해당 시간복잡도를 해결하는 방법을 떠올리지 못해 다른 풀이를 참고했습니다.

대부분의 풀이가 시간복잡도를 신경쓰지 않고 풀었더라구요. 문제 요구사항에 적혀있는데, 시간복잡도를 지키지 않아도 코드가 통과하나봅니다.

브루트 포스

가장 쉽게 떠올릴 수 있는 아이디어는 두 배열을 하나로 합친 뒤, 가운데 값을 찾는 겁니다. 하지만 이 방식은 시간복잡도가 N * logN 으로 적합하지 않습니다.

투포인터(like 분할정복)

"정렬되어 있는 두 배열을 하나의 배열로 만든다" 이 아이디어는 분할정복의 아이디어와 일치합니다.
투포인터 개념을 사용해서 두 배열을 합치면 앞선 브루트포스보다 더 빠른 시간복잡도를 낼 수 있습니다. 하지만 여전히 N의 시간복잡도가 소요됩니다.

실제 풀이

문제에서 시간복잡도를 엄격하게 검사하지 않습니다. 인터넷에 풀이를 찾아보면 시간복잡도를 고려하지 않고 푼 풀이들이 대부분입니다. 그러니까 이 분 설명을 읽는 걸 추천드립니다. 제가 더 잘 설명할 자신이 없어 링크로 대체하겠습니다.
해당 블로그 글을 정독하면서 흐름을 따라가다보면 이해할 수 있을겁니다. 수학적 공식들이 적혀 있는데 해당 부분에 초점을 맞춰서 따라가다보면 이해할 수 있을겁니다.

자바 코드는 아래 첨부해두겠습니다.

코드

아, 해당 풀이에서 while 반복문을 무한루프를 돌렸습니다.
low와 high의 비교를 통해 mid를 찾는 문제가 아니기 때문입니다.
정답이 나오는 로직이 별도로 있어서 while문 조건에 low<high 를 넣지 않았습니다.

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] small;
        int[] big;
        if (nums1.length < nums2.length) {
            small = nums1;
            big = nums2;
        } else {
            small = nums2;
            big = nums1;
        }

        int m = small.length;
        int n = big.length;
        
        // 배열이 하나밖에 없는 경우(배열 한 개의 크기가 0)
        if (m == 0) {
            if (n % 2 == 0) {
                return (big[big.length / 2 - 1] + big[big.length / 2]) / 2.0;
            }
            return big[big.length /2];
        }

        int low = 0;
        int high = m;
        
        while(true) {
            int i = (low + high)/2; //i는 mid
            int j = (m+n)/2 - i;

            int smallLeft = -99999999;
            if (i-1 >= 0) {
                smallLeft = small[i-1];
            }

            int bigLeft = -99999999;
            if (j-1 >= 0) {
                bigLeft = big[j-1];
            }

            int smallRight = 99999999;
            if (i != small.length) {
                smallRight = small[i];
            }

            int bigRight = 99999999;
            if (j != big.length) {
                bigRight = big[j];
            }

            if (smallRight < bigLeft) {
                low = i + 1;
                continue;
            } else if (bigRight < smallLeft) {
                high = i;
                continue;
            }

            //정답이 나온다
            int left = Math.max(smallLeft, bigLeft);
            int right = Math.min(smallRight, bigRight);
            if ((small.length + big.length) % 2 == 0) {
                return (left + right) / 2.0;
            }
            return right;
        }
    }
}