[Leetcode(릿코드)/4] Median of Two Sorted Arrays (Hard, Java)

Question

• 문제 링크 : https://leetcode.com/problems/median-of-two-sorted-arrays/
• 분류 : 우선순위큐
• 풀이 시간 : 10분

문제 해설

1. 크기가 n인 num1와 크기가 m인 num2인 배열이 주어진다
2. 이 두 배열 값의 중앙 값을 구하여라
   1. 딱 떨어지는 중앙값이 없을 경우(= 두 배열을 합친 길이가 짝수일 때), 중앙에 가까운 양 쪽 값의 평균값으로 리턴
3. 시간 복잡도는 $O(log (n+m)$

Solution

풀이 접근 방법

1. 두개의 우선순위 큐로 나누어서 수 정렬
   1. 중앙 기준, 작은 값을 담는 우선순위 큐 : 내림차순 정렬
   2. 중앙 기준, 큰 값을 담는 우선순위 큐 : 오름차순 정렬
   3. 두 우선순위 큐의 맨 위에 있는 값들은 자동적으로 중앙 값을 표현하고 있음

정답 코드

import java.util.*;

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        PriorityQueue<Integer> minQueue = new PriorityQueue<Integer>(Collections.reverseOrder());
        PriorityQueue<Integer> maxQueue = new PriorityQueue<Integer>();
        
        for (int i = 0; i < nums1.length; i++) {
            // 큐에 들어가 있는 숫자의 개수에 따라 번갈아서 넣어 줌
            if (maxQueue.size() < minQueue.size()) {
                maxQueue.add(nums1[i]);
            } else {
                minQueue.add(nums1[i]);
            }
            
            if (!minQueue.isEmpty() && !maxQueue.isEmpty()) {
                // 큰 값이 들어가있는 큐의 제일 작은 값이, 작은 값이 들어가있는 큐의 제일 큰 값보다 작을 경우
                // 둘을 바꿔서 넣어줌
                if (minQueue.peek() > maxQueue.peek()) {
                    int temp = minQueue.poll();
                    minQueue.add(maxQueue.poll());
                    maxQueue.add(temp);
                }
            }
        }
        
        for (int i = 0; i < nums2.length; i++) {
            if (maxQueue.size() < minQueue.size()) {
                maxQueue.add(nums2[i]);
            } else {
                minQueue.add(nums2[i]);
            }
            
            if (!minQueue.isEmpty() && !maxQueue.isEmpty()) {
                if (minQueue.peek() > maxQueue.peek()) {
                    int temp = minQueue.poll();
                    minQueue.add(maxQueue.poll());
                    maxQueue.add(temp);
                }
            }
        }
        
        // 딱 떨어지는 중앙값 없으면, 양 옆 숫자의 평균 리턴
        if(maxQueue.size() == minQueue.size()) {
            return (maxQueue.poll() + minQueue.poll()) / 2.0;
        } else if (maxQueue.size() > minQueue.size()) {
            return (double) maxQueue.poll();
        } else {
            return (double) minQueue.poll();
        }
        
    }
}