LeetCode: 4번 (Median of Two Sorted Arrays) [JAVA]

문제 링크

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

Median of Two Sorted Arrays - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. merge sort의 과정 중 하나인 merge 과정을 주어진 두 배열에 진행
2. 이후 만들어진 전체 배열에서 중위값을 찾아 반환

 문제에서 이미 정렬된 배열 2개가 주어지고 이를 통합해야 하는데, 만약 이걸 단순히 합치고 다시 정렬을 진행하려하면 복잡도 측면에서 좋지 않다. 다만 정렬을 공부하다 보면 이러한 형태가 많이 익숙한데, 바로 정렬된 2개의 배열이 주어지고, 이를 합해야 한다는 측면에서 merge sort를 떠올릴 수 있다. 

 그렇기 때문에 애초에 두 배열 길이 크기를 합한만큼의 배열을 선언해놓고 두 배열 요소를 비교해 가며 통합할 배열을 채워나가면, 상대적 적은 복잡도로 배열을 만들어 낼 수 있고, 이후 단순히 중위값을 계산해서 반환하면 된다.

 

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] merge = new int[nums1.length + nums2.length];
        int nums1Index = 0, nums2Index = 0, index=0;

        while (nums1Index < nums1.length && nums2Index < nums2.length) {//두 배열을 통함
            if (nums1[nums1Index] < nums2[nums2Index]) {
                merge[index++] = nums1[nums1Index++];
            } else {
                merge[index++] = nums2[nums2Index++];
            }
        }

        if (nums1Index == nums1.length) {//첫 번째 배열에 남은게 없다면
            while (nums2Index < nums2.length) {
                merge[index++] = nums2[nums2Index++];
            }
        }

        if (nums2Index == nums2.length) {//두 번째 배열에 남은게 없다면
            while (nums1Index < nums1.length) {
                merge[index++] = nums1[nums1Index++];
            }
        }
        
        if (merge.length % 2 == 0) {//중위값 계산
            return (double) (merge[merge.length / 2 - 1] + merge[merge.length / 2]) / 2.0;
        } else {
            return (double) merge[merge.length / 2];
        }
    }
}

결과