[알고리즘] 4. Median of Two Sorted Arrays

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

 

두 배열을 합쳐서 중간값을 구하는 알고리즘 문제입니다.

 

일단 for 문을 사용해서 리스트를 합치다가 리스트에 존재하는 addAll() 생각이 나서 적용을 해보았습니다.

그래서 간단하게 [...배열1, ...배열2].sort() 형태로 간단하게 만들었습니다.

class Solution {
  double findMedianSortedArrays(List<int> nums1, List<int> nums2) {
    List<int> total = [...nums1, ...nums2]..sort();

    int totalLen = total.length;
    int halfLen = (total.length / 2).toInt();

    if (totalLen % 2 == 1) {
      return total[halfLen].toDouble();
    } else {
      return (total[halfLen - 1] + total[(halfLen)]) / 2;
    }
  }
}

 

역시 간단하게 해결했지만 큰 노력없이 리스트에 추가 및 정렬을 해서 점수는 좋지 않았습니다.

 

 

여기에 추가로 좀 더 빠르고 낭비를 줄일 수 있는 알고리즘을 2가지 적용이 가능함을 알게 되었습니다.

1. 투 포인터 병합 방식

double findMedianSortedArrays2(List<int> nums1, List<int> nums2) {
    int m = nums1.length;
    int n = nums2.length;
    
    int total = m + n;
    int targetIndex = total ~/ 2;
    int count = 0;
    int i = 0, j = 0;
    int current = 0, prev = 0;

    while (count <= targetIndex) {
      prev = current;
      if (i < m && (j >= n || nums1[i] < nums2[j])) {
        current = nums1[i++];
      } else {
        current = nums2[j++];
      }
      count++;
    }

    if (total % 2 == 1) return current.toDouble();
    return (prev + current) / 2.0;
  }

 

위에 상대적으로 편하게 생각할 수 있는 방식으로 풀기 전에 머리로는 투포인터 병합 방식(?) 조금 비슷한게 떠올리긴했으나 구현을 하지 못했었습니다. 

 

2. 파티션과 이진 탐색 방법

이진 탐색 방법을 통해서 시간 복잡도를 O(log(m+n)) 로 동작하게 하는 정답 방식은 다음과 같습니다.

사실 이 방식은 봐도봐도 이해가 잘 가지 않았고 머리에 조금이라도 넣는데 시간이 많이 걸렸습니다. ㅠㅠ

class Solution {
  double findMedianSortedArrays(List<int> nums1, List<int> nums2) {
    if (nums1.length > nums2.length) {
      return findMedianSortedArrays(nums2, nums1);
    }

    int m = nums1.length;
    int n = nums2.length;
    int low = 0;
    int high = m;

    while (low <= high) {
      int partitionX = (low + high) ~/ 2;
      int partitionY = (m + n + 1) ~/ 2 - partitionX;

      double maxLeftX = (partitionX == 0)
          ? double.negativeInfinity
          : nums1[partitionX - 1].toDouble();

      double minRightX = (partitionX == m)
          ? double.infinity
          : nums1[partitionX].toDouble();

      double maxLeftY = (partitionY == 0)
          ? double.negativeInfinity
          : nums2[partitionY - 1].toDouble();

      double minRightY = (partitionY == n)
          ? double.infinity
          : nums2[partitionY].toDouble();

      if (maxLeftX <= minRightY && maxLeftY <= minRightX) {
        if ((m + n) % 2 == 0) {
          return (max(maxLeftX, maxLeftY) + min(minRightX, minRightY)) / 2;
        } else {
          return max(maxLeftX, maxLeftY);
        }
      } else if (maxLeftX > minRightY) {
        high = partitionX - 1;
      } else {
        low = partitionX + 1;
      }
    }
    throw Exception("입력 배열이 정렬되어 있지 않습니다.");
  }
}

 

이진 탐색을 통해서 모든 리스트 혹은 배열을 돌기보다 중앙값을 찾은 후 그 방향에서 좌측 혹은 우측 방향으로 이동하면서 맞는 값을 찾아나감으로 인해서 최소한 반은 덜 이동하게 됩니다. 더불어서 무식한 방식(Brute Force) 방식으로 할때는 모든 배열을 넣는 과정 더불어서 정렬하는 과정 등을 모두 작업하게되면 리스트 혹은 배열이 늘어날 수록 훨씬 더 시간이 늘어나게 됩니다. 그렇기에 처음 볼때는 어렵지만 계속 보고 또 보고를 반복하다보면 조금은 머리에 들어올 수 있는 이진 탐색 방법을 학습해보면 좋을것 같습니다.