[leetcode] Medium-4번. median-of-two-sorted-arrays 문제풀이

문제

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

Median of Two Sorted Arrays - LeetCode

 

 

 

풀이코드

package SITE03_leetcode.medium;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/median-of-two-sorted-arrays
 */
public class M004_leetCode4_median_of_two_sorted_arrays {
    private int lo, maxLen;

    public static void main(String[] args) {
        M004_leetCode4_median_of_two_sorted_arrays solution = new M004_leetCode4_median_of_two_sorted_arrays();

        int[] a = new int[]{2};
        int[] b = new int[]{};

        System.out.println(solution.findMedianSortedArrays(a, b));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] mergeArr = new int[nums1.length + nums2.length];
        double sum = 0;

        /* 합치기 */
        int index = 0;
        for (int j : nums1) {
            mergeArr[index] = j;
            index++;
        }

        for (int j : nums2) {
            mergeArr[index] = j;
            index++;
        }

        /* 정렬 */
        Arrays.sort(mergeArr);

        int division = 0;

        /* 가운데 인덱스 뽑기 */
        if (mergeArr.length % 2 == 0) { /* 짝수의 경우 */
            division = 2;
            int target = (mergeArr.length + 1) / 2;

            sum = mergeArr[target - 1] + mergeArr[target];
        } else { /* 홀수의 경우 */
            division = 1;
            int target = (mergeArr.length + 1) / 2;

            sum = mergeArr[target - 1];
        }

        return sum / division;
    }
}

 

풀이 코드의 순서는 다음과 같다.

1) 배열을 합친다.
2) 정렬한다.
3) 해당 배열의 개수가 짝수인지 홀수인지 판단한다.
4) 홀수일 경우, 배열의 [target - 1] 인덱스의 1개 값을 갖고, 짝수일 경우 [target - 1], [target] 인덱스의 2개 값을 갖는다.
5) 짝수일 경우는 변수 sum 의 값을 2로 나누고, 홀수일 경우에는 1로 나눈다.

 

 

 

배열을 합치지 않는 풀이코드

위 나의 풀이 코드는 배열을 합침으로써 아주 간단한 문제가 되었다. 만일, 배열을 합치지않고 풀이를 하라고 한다면? 이라는 의문이 들어, 아래 풀이코드를 참고했다.

 

https://leetcode.com/problems/median-of-two-sorted-arrays/discuss/2791/25-lines-Java-Solution님의 풀이

package SITE03_leetcode.medium;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/median-of-two-sorted-arrays
 */
public class M004_leetCode4_median_of_two_sorted_arrays_다른풀이 {
    private int lo, maxLen;

    public static void main(String[] args) {
        M004_leetCode4_median_of_two_sorted_arrays_다른풀이 solution = new M004_leetCode4_median_of_two_sorted_arrays_다른풀이();

        int[] a = new int[]{1, 3};
        int[] b = new int[]{2};

        System.out.println(solution.findMedianSortedArrays(a, b));
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length; // nums1 배열의 크기
        int n = nums2.length; // nums2 배열의 크기

        int k = (m + n) / 2; // 위 두 배열의 크기를 2로 나눈 값
        int i = 0;
        int j = k;
        int lo = 0;
        int hi = Math.min(k, m); // k 와 nums1 배열의 크기인 m 의 최소 값 저장

        while (true) {
            /* 각 원소를 비교할 인덱스 i, j */
            i = lo + (hi - lo) / 2;
            j = k - i;

            /* 원소의 크기 비교 */
            /* CASE1. nums1 의 원소가 더 클 경우 */
            if (get(nums1, i) >= get(nums2, j - 1)) {
                /* CASE2. nums2 의 원소가 더 클 경우 */
                if (get(nums2, j) >= get(nums1, i - 1)) {
                    break;
                } else {
                    hi = i - 1;
                }
            } else {
                lo = i + 1;
            }
        }

        /** 홀수일 경우 */
        if ((m + n) % 2 == 1) {
            return Math.min(get(nums1, i), get(nums2, j)); // odd
        }

        /** 짝수일 경우 */
        return (double)(Math.min(get(nums1, i), get(nums2, j))
                        + Math.max(get(nums1, i - 1), get(nums2, j - 1))) / 2; //even
    }

    private int get(int[] nums, int i) {
        /* 0 보다 작은 경우 */
        if (i < 0) {
            return Integer.MIN_VALUE;
        }

        /* i 가 매개변수 nums 의 길이보다 크거나 같으면 */
        if (i >= nums.length) {
            return Integer.MAX_VALUE;
        }

        /* nums 배열에서 i 번째의 값을 리턴 */
        return nums[i];
    }
}