[LeetCode][Java] Median of Two Sorted Arrays

최지수·2021년 9월 27일

Algorithm

목록 보기

10/77

첫 Hard 난이도 문제입니다. 도전적인 문제였습니다. 그리고 다른 방식의 접근을 알 수 있게 되었어요.

문제

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)).

제한사항

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
$-10^6$ <= nums1[i], nums2[i] <= $10^6$

접근1

두 개의 정렬된 배열이 있을 때 두 배열 요소 중 중간 값Median을 찾으라는 문제였습니다. 간단해 보이는 문제로 보이지만, 시간복잡도 O(log (m+n))을 요구하는 문제에요.

배열을 합치고 아무리 빠른 정렬을 수행한들 O((m+n)log (m+n))이 걸리고, 병합 정렬을 응용한들 O(m+n)이라 느릴 수 밖에 없습니다.

그래서 처음 시도한 것은 이분탐색binary search였어요. 중간 위치의 값을 구하고, 두 수를 비교해서 작은 숫자의 경우 오른쪽을 기준으로, 큰 숫자의 경우 왼쪽을 기준으로 해서 중간 값을 점차 좁혀나가는 걸 생각했습니다.

하지만 모든 배열 내 숫자가 중복 가능성이 있어 불완전한 답을 도출할 수 밖에 없었습니다.

답안1(실패)

class Solution{
	public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if(nums1.length == 0 && nums2.length == 0)
            return 0d;

        double answer= 0;

        int left1 = 0, right1 = nums1.length - 1;
        int left2 = 0, right2 = nums2.length - 1;
        int candidate1 = Integer.MAX_VALUE, candidate2 = Integer.MAX_VALUE;
        while(left1 <= right1 || left2 <= right2){
            int mid1 = (left1 + right1) >> 1;
            if(left1 <= right1){
                candidate1 = nums1[mid1];
            }

            int mid2 = (left2 + right2) >> 1;
            if(left2 <= right2){
                candidate2 = nums2[mid2];
            }

            if(candidate1 == candidate2)
                break;

            if(candidate1 < candidate2){
                left1 = mid1 + 1;
                right2 = mid2 - 1;
            }
            else{
                right1 = mid1 - 1;
                left2 = mid2 + 1;
            }
        }
        if(nums1.length != nums2.length)
            answer = (candidate1 < candidate2) ? candidate1 : candidate2;
        else
            answer = (candidate1 + candidate2) / 2d;
        return answer;
    }
}

접근2

목표 시간이 되기 전에 이에 대한 예외 처리를 추가하는 것을 시도했지만 막혔습니다... 결국에 답을 참고하기로 했어요.

생각보다 이분 탐색을 응용한 풀이를 보진 못했습니다. 그러다 우선순위 큐Priority Queue를 활용한 풀이를 보았습니다.

우선순위 큐를 활용한 풀이

굉장히 독특한 발상의 전환이라 생각했습니다. 생각해보니 우선순위 큐Priority Queue는 삽입과 추출이 모두 O(log(n))이었어요.

이렇게 된다면 모든 배열을 큐에 넣어서 중간 값을 도출하면 결과적으로 시간 복잡도가 O(log(n))이 되는 것이었습니다! O(log(n))에 대한 풀이 방법을 하나 찾은 기분이 들어 바로 작업에 들어갔고, 결과는 Accepted였습니다.

답안2(풀이 봄)

class Solution{
	
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        for(int num : nums1)
            pq.add(num);
        for(int num : nums2)
            pq.add(num);

        double answer = 0d;

        int totalSize = pq.size();
        if(totalSize % 2 == 0) {
            int value1 = 0, value2 = 0;
            for(int i = 0 ; i < totalSize; ++i){
                int value = pq.poll();
                if(i == (totalSize >> 1) - 1){
                    value1 = value;
                }
                else if(i == (totalSize >> 1)){
                    value2 = value;
                    break;
                }
            }
            answer = (value1 + value2) / 2d;
        }
        else{
            for(int i = 0 ; i < totalSize; ++i){
                int value = pq.poll();
                if(i == (totalSize >> 1)){
                    answer = value;
                    break;
                }
            }
        }
        return answer;
    }

}