LeetCode Median of Two Sorted Arrays (JavaScript), Binary Search, Two Pointer

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

문제 설명

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• 106 <= nums1[i], nums2[i] <= 106

---

문제 풀이

중앙 값을 구하는 문제로 O(log (m + n))의 시간복잡도로 해결을 해야한다.

결국 일반적인 sort로 접근을 하면 위 시간복잡도로 문제를 해결할 수 없다.

 

1. Two Pointer 이용 (투 포인터, O(m + n))

조건

• 두 배열을 합친 길이가 짝수인 경우 중앙 값은 2개를 더한 값으로 구해야 한다.
• 홀수인 경우 1개의 중앙 값만 존재한다.

접근 방식

1. prev, curr로 이전 값, 현재 값을 구한다. (짝수 / 홀수를 대비하기 위해)
2. 두 개의 포인터 p1, p2로 각 nums1, nums2의 배열의 index 값을 나타낸다.
3. 모든 배열 탐색하는 것이 아닌 두 배열의 길이의 합의 절반 만큼만 진행
   • 각 위치에서 작은 값을 기준으로 포인터 값을 1씩 증가 시켜 나감
4. 최종적으로 중앙 값을 계산
   • 전체 길이가 짝수인 경우 (prev + curr) / 2 가 중앙값
   • 홀수인 경우 curr이 중앙값 (1개 이므로 2로 나눌 필요 없음)

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    const len1 = nums1.length;
    const len2 = nums2.length;
    const totalLen = len1 + len2

    const mid = Math.floor(totalLen / 2);
    let [prev, curr] = [0, 0];
    let [p1, p2] = [0, 0];
    
    for (let i = 0; i <= mid; i++) {
        prev = curr;

        if (p1 < len1 && (p2 >= len2 || nums1[p1] <= nums2[p2])) {
            curr = nums1[p1];
            p1++;
        } else {
            curr = nums2[p2];
            p2++;
        }
    }

    if (totalLen % 2 === 0) {
        return (prev + curr) / 2;
    } else {
        return curr;
    }
};

---

2. Binary Search (이분 탐색 이용, O(log(min(m, n)))

변수 정리

1. part1 : nums1에서 왼쪽으로 보내는 원소 개수
2. part2 : nums2에서 왼쪽으로 보내는 원소 개수 (총 길이 절반 - part1)
3. maxLeft1 : nums1 왼쪽 부분의 최댓값
4. minRight1 : nums1 오른쪽 부분의 최솟값
5. maxLeft2 : nums2 왼쪽 부분의 최댓값
6. minRight2 : nums2 오른쪽 부분의 최솟값

 

핵심 방법

• 중앙값이란 결국 "전체 원소의 절반은 왼쪽, 절반은 오른쪽"이 되는 경계이다. 이를 이용해 문제를 다르게 바라볼 수 있다.
• 두 배열 nums1, nums2를 각각 왼쪽/오른쪽으로 나누는 분할점(partition)을 잡고, 아래 두 조건을 만족하면 된다.
  • maxLeft1 <= minRight2 (nums1의 왼쪽 최댓값 <= nums2의 오른쪽 최솟값)
  • maxLeft2 <= minRight1 (nums2의 왼쪽 최댓값 <= num1의 오른쪽 최솟값)
• 위 두 조건을 만족하면 두 배열을 합쳐서 정렬했을 때 왼쪽 절반과 오른쪽 절반을 정렬된 상태로 나눌 수 있다.

왜 위와 같은 조건을 만족해야 하나? (보충 설명)

위 문제의 핵심은 정렬된 상태를 만드는게 아니라 분할점을 기준으로 정렬이 된다고 가정을 했을 경우 왼쪽에 오는 값들의 집합 + 오른쪽에 오른 값들의 집합을 구하는 것이 핵심임.

결국 분할점을 기준으로 왼쪽 집합, 오른쪽 집합을 만들었을 때, 왼쪽 집합의 최댓값이 오른쪽 집합의 최솟값보다 작거나 같으면 실제로 정렬하지 않아도 "이 분할은 올바르다"고 확신할 수 있다. 두 조건(maxLeft1 ≤ minRight2, maxLeft2 ≤ minRight1)은 바로 그것을 두 배열에 교차로 검증하는 것이다.

 

주의 사항

• 이진 탐색을 긴 배열을 기준으로 하게되면 part2가 음수가 될 수 있으므로, 항상 짧은 배열이 nums1이 되도록 해야한다.
• 경계값 (-Infinity, Infinity) 처리를 안하게되면 part1 = 0 이거나 part2 = len1일 때 잘못된 index를 참조하게 된다.
• part2 계산 시 (len1 + len2 + 1) / 2에서 +1을 안하면 홀수 길이일 때 잘못된 중앙값을 갖게된다.

 

[ [1, 3, 8] / [7, 9, 10, 11] 의 중앙값 찾는 과정 시각화 ]

 

중앙값 구하는 방법

1. 홀수 길이인 경우
   • 올바른 분할이 완성된 순간 위 예제의 경우 { 1, 3, 7, 8 } | {9, 10, 11} 로 나뉘어진다.
   • 즉, 중앙값은 8의 위치한 자리로 왼쪽 집합을 기준 가장 끝 값을 나타낸다.
     • Math.max(maxLeft1, maxLeft2)를 구하면 된다.

• 짝수 길이인 경우
  • 올바른 분할이 완성된 순간 { ... , a } | { b, ... }로 나뉘어지고 중앙 값은 ( a + b ) / 2의 값을 나타낸다.
    • (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2를 구하면 된다.

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function(nums1, nums2) {
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }

    const len1 = nums1.length;
    const len2 = nums2.length;
    let [left, right] = [0, len1];

    while (left <= right) {
        const part1 = Math.floor((left + right) / 2);
        const part2 = Math.floor((len1 + len2 + 1) / 2) - part1;

        const maxLeft1 = part1 === 0 ? -Infinity : nums1[part1 - 1];
        const minRight1 = part1 === len1 ? Infinity : nums1[part1];
        const maxLeft2 = part2 === 0 ? -Infinity : nums2[part2 - 1];
        const minRight2 = part2 === len2 ? Infinity : nums2[part2];

        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            if ((len1 + len2) % 2 === 0) {
                return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
            } else {
                return Math.max(maxLeft1, maxLeft2);
            }
        } else if (maxLeft1 > minRight2) {
            right = part1 - 1;
        } else {
            left = part1 + 1;
        }
    }
};

---

결론

이 문제의 핵심은 "중앙값을 찾는 문제"를 "올바른 분할점을 찾는 문제"로 재정의한 것이 핵심이다.

문제를 재정의하고 이 문제를 Binary Search를 통해 해결해야 하는 문제로 생각보다 어려운 Binary Search 문제라고 생각이 든다.

 

최대한 이해하기 쉽게 작성은 했지만 생각보다 이해하기가 어려운 문제인 것 같다.