[99클럽 코테 스터디 15일차 TIL] 이분탐색

📖 오늘의 학습 키워드
이분탐색

오늘의 회고

문제

[K-th Smallest Prime Fraction]
https://leetcode.com/problems/k-th-smallest-prime-fraction/description/

나의 해결

class Solution {
    public int  first, second;
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int[] answer = new int[2];
        double left = 0;
        double right = 1;
        while(left <= right) {
            double mid = (left + right) / 2;
            if(calculate(mid ,arr) == k) {
                answer[0] =  arr[first];
                answer[1] = arr[second];
                break;
            }
            else if(calculate(mid ,arr) > k) {
                right = mid;
            }
            else {
                left = mid;
            }
        }
        return answer;
    }
    public int calculate(double mid, int[] arr) {
        int idx = 0;
        int j = 1;
        double max = 0;
        for(int i = 0; i < arr.length; i++) {
            while(j < arr.length && arr[i] /(double)arr[j] >= mid) {
                j++;
            }
            idx += arr.length - j;
            if(j < arr.length && max < arr[i] /(double)arr[j]) {
                max = arr[i] /(double)arr[j];
                first = i;
                second = j;
            }
        }
        return idx;
    }
}

1. left는 0, right는 1로 초기화한다. left와 right로 임의의 분수를 구한다.

   • arr[i] / arr[j] (0 <= i < j < arr.length)
     arr 배열은 오름차순으로 정렬되어 있고 배열 안에 같은 수는 없으므로 위 조건을 만족하는 분수는 0보다 크고 1보다 작을 수밖에 없다.

2. 이분탐색을 진행한다.
   1) 임의의 분수 값인 mid를 left와 right의 반값으로 구한다.
   2) arr 배열로 만들 수 있는 분수 값 중 mid 값보다 작거나 같은 것의 개수를 찾는다.

   • idx는 mid 값보다 작거나 같은 것의 개수이다. 처음에는 0으로 초기화한다.
   • j 값는 i보다 커야 하므로 1로 초기화 한다.
   • i 값이 0부터 arr.length-1까지 arr를 순회하며 mid보다 작거나 같은 분수의 개수를 찾는다.
   • arr[i] /(double)arr[j]가 mid 값보다 크거나 같을 때까지 j 값을 하나씩 늘려간다.
   • mid 값보다 작거나 같은 것의 개수를 구하는 것이므로 idx 에는 arr의 길이에서 j를 뺀 값을 더한다.
   • mid 값보다 작거나 같은 것의 개수가 k와 같을 때 분모, 분자값을 정답으로 반환해 주어야 하기 때문에 mid 값보다 작거나 같은 분수 중 최댓값을 저장하고 최댓값일 때 분모, 분자값의 인덱스를 first(분자)와 second(분모)에 저장한다.

   3) mid보다 작거나 같은 값들의 개수가 k와 같다면 위의 과정에서 찾은 최대값의 분자와 분모 값을 반환한다.
   4) k보다 크다면, mid 값이 더 작아져 개수를 줄여야 한다. right를 mid로 한다.
   5) k보다 작다면, mid 값이 더 커져야 한다. left를 mid로 한다.

새로 학습한 내용