[LeetCode] 786. K-th Smallest Prime Fraction

https://leetcode.com/problems/k-th-smallest-prime-fraction/description/

leetcode - K-th Smallest Prime Fraction

문제 유형 : 이진탐색, 브루트 포스

문제 난이도 : Medium

 

문제

You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.

For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].

Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].

 

1과 정수들로 이루어진 배열 arr이 오름차순정렬 되어있다.

값들은 겹치지 않는다.

당신은 정수 k를 받는다.

 

후위부의 숫자를 분모로 하고, 전위부의 숫자를 분자로 하여 분수를 만들었을 때, k번째로 작은 것을 구하시오.

정답은 분자와 분모를 2짜리 배열로 감싸야 합니다.

 

풀이

1. 브루트 포스

모든 가능한 분수 조합들을 만들어서, 정렬시키고, 조합 배열의 k-1번쨰 요소를 반환한다.

 

2. 이진탐색을 이용한 풀이

https://leetcode.com/problems/k-th-smallest-prime-fraction/solutions/5137467/fastest-100-easy-clean-concise-multiple-approaches/

(고마워요 스파이더맨)

 

처음에, left = 0, right = 1로 한다.

그 뒤, mid값을 구한다.

mid값보다 작거나 같은 숫자들의 개수를 구한다.

만약 개수가 딱 k개라면, 구하는 과정에서 얻은 최고 크기의 분수 조합을 반환한다.

만약 개수가 k보다 크다면, 더 작은 숫자 범위에서 찾아야 한다. right을 mid로 한다.

아니라면, 더 큰 숫자 범위에서 찾아야 한다. left를 mid로 한다.

이를 계속 반복한다.

 

코드

C++ - 브루트 포스

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        int n = arr.size();
        vector<vector<int>> ans;

        for(int i = 0; i < n-1; i++) {
            for(int j = i+1; j < n; j++) {
                ans.push_back({arr[i], arr[j]});
            }
        }

        sort(ans.begin(), ans.end(), [](const auto &a, const auto &b){
            return double(a[0])/a[1] < double(b[0])/b[1];
        });

        return ans[k-1];
    }
};

 

C++ - 이진탐색을 이용한 풀이

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        int n = arr.size();
        double left = 0, right = 1, mid;
        vector<int> ans;

        while(left <= right) {
            mid = (left + right)/2;
            int j = 1, total = 0, num = 0, den = 0;
            double maxFrac = 0;

            for(int i = 0; i < n; i++) {
                while(j < n && double(arr[i])/arr[j] >= mid) {
                    j++;
                }

                total += n - j;

                if(j < n && maxFrac < double(arr[i])/arr[j]) {
                    maxFrac = double(arr[i])/arr[j];
                    num = i;
                    den = j;
                }
            }

            if(total == k) {
                ans = {arr[num], arr[den]};
                break;
            }

            if(total > k) {
                right = mid;
            } else {
                left = mid;
            }
        }

        return ans;
    }
};