[getItemFromTwoSortedArrays] 두 배열에서 K번째로 큰 수 구하기

문제

주어진 두 배열의 요소 중 k번째로 큰 수 구하기

I1, I2 : 정수로 된 int [ ] arr1 , arr2

I3 : 0 이상의 자연수 k

O : k번째로 큰 정수

public static void main(String[] args) {
    int[] arr1 = new int[]{1, 4, 8, 10};
    int[] arr2 = new int[]{2, 3, 5, 9};
    int result = getItemFromTwoSortedArrays(arr1, arr2, 6);
    System.out.println(result);
}

나의풀이

: 두 배열을 하나로 합쳐서 sort 후 구하기

import java.util.*;

// 배열 합쳐버리는 방법
import static java.util.Arrays.copyOf;

public class getItemFromTwoSortedArrays {
    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 4, 8, 10};
        int[] arr2 = new int[]{2, 3, 5, 9};
        int result = getItemFromTwoSortedArrays(arr1, arr2, 6);
        System.out.println(result);
    }

    // 코드 구현 부분
    public static int getItemFromTwoSortedArrays(int[] arr1, int[] arr2, int k) {
        // TODO:
        int[] arr3 = copyOf(arr1,arr1.length+arr2.length);
        for(int i=0 ; i<arr2.length ; i++) {
            arr3[i+arr1.length] = arr2[i];
        }
        Arrays.sort(arr3);
        return arr3[k-1];
    }
}

 

레퍼런스

: 이진 트리 검색

// 이진 탐색 트리
public class reference {
    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 4, 8, 10};
        int[] arr2 = new int[]{2, 3, 5, 9};
        int result = getItemFromTwoSortedArrays(arr1, arr2, 6);
        System.out.println(result);
    }

    public static int getItemFromTwoSortedArrays(int[] arr1, int[] arr2, int k) {
        int leftIdx = 0;
        int rightIdx = 0;
        while (k > 0) {
            // 각 배열에서 k를 절반으로 쪼개서 카운트
            int cnt = (int) Math.ceil(((double) k) / 2);
            int leftStep = cnt;
            int rightStep = cnt;

			// -------------------------------------------------------------------
            // 엣지 케이스 1
            // 카운트가 남았음에도 배열의 끝에 도달한 경우
            // : k를 나머지 배열쪽으로 넘김
            if (leftIdx == arr1.length) {
                rightIdx = rightIdx + k;
                break;
            }

            if (rightIdx == arr2.length) {
                leftIdx = leftIdx + k;
                break;
            }
            // 엣지 케이스 2
            // 현재 카운트가 남아있는 후보 요소들보다 많을 경우
            // : leftStep(현재 할당량)을 남아있는 요소들의 개수로 변경
            if (cnt > arr1.length - leftIdx) leftStep = arr1.length - leftIdx;
            if (cnt > arr2.length - rightIdx) rightStep = arr2.length - rightIdx;
			// -------------------------------------------------------------------

            // 두 배열의 현재 검사 요소 위치를 비교해서, 그 값이 작은 배열은 비교한 위치 앞에 있는 요소들을 모두 후보군에서 제외
            if (arr1[leftIdx + leftStep - 1] < arr2[rightIdx + rightStep - 1]) {
                leftIdx = leftIdx + leftStep;
                // 처리가 끝나면 k값을 절반으로
                k = k - leftStep;
            } else {
                rightIdx = rightIdx + rightStep;
                k = k - rightStep;
            }
        }
        int leftMax = (leftIdx - 1 < arr1.length) ? arr1[leftIdx - 1] : -1;
        int rightMax = (rightIdx - 1 < arr2.length) ? arr2[rightIdx - 1] : -1;

        return Math.max(leftMax, rightMax);
    }
}

 

깃 링크

https://github.com/PNUHCT/AlgorismStorage.git