99클럽 코테 스터디 23일차 TIL - 이분탐색 (LeetCode '786. K-th Smallest Prime Fraction')

항해99 코테 스터디 22일차 문제인 리트코드  786번 문제는 정수 배열에서 두 수를 뽑아 만드는 분수들 중 k번째를 찾는 문제다. 난이도는 Medium이며 완전탐색 또는 이분탐색을 통해 해결할 수 있다.

 

오늘의 문제 - K-th Smallest Prime Fraction 문제 정보

문제 키워드

- BS

난이도

- Medium

 

문제 요약

• 1과 소수로만 이루어진 오름차순 정수 배열 arr가 주어진다. (배열 내의 정수는 중복되지 않는다)
• 0 ≤ i < j < arr.length인 모든 (i, j)에 대해 분수 arr[i]/arr[j]를 계산했을 때, k번째로 작은 분수를 구하여 정답으로 [arr[i], arr[j]]를 반환하여라.

 

문제 풀이 과정  

•  

• N≤10000이라서 O(N^2)으로도 풀리지만, 키워드가 이진탐색인 만큼 더 작은 시간복잡도로 풀어보려 하였다. (O(NlogN)정도)
• 이진 탐색을 사용하기 위해서, 어떤 것을 범위로 잡고 어떤 조건을 이용해 범위를 줄여나갈 것인지를 결정해야 했다.
  • 분수를 계산하는 문제이기 때문에 0~1을 시작 범위로 하고 반씩 줄여나가면 어떨까 생각은 했는데, 중간값보다 작은 분수의 개수를 구하는 것이 O(N^2)로 구하는 방법 말고는 떠오르지가 않았다.
  • GPT와 많은 씨름을 한 끝에… 정렬된 배열에서 두 수를 뽑아 분수를 만들었을 때, 특정 값보다 작은 분수의 개수를 구하는 O(N)짜리 방법을 알게 되었다.
• 따라서 이진탐색으로 low와 high의 범위를 줄여갈 때 사용되는 조건으로, mid값보다 작거나 같은 분수의 개수가 k개 미만/초과/같은 경우에 따라 다음 루프로 넘어가도록 하였다.
  • 여기서 k개와 같아진다면, mid보다 작거나 같은 가장 큰 분수를 반환한다.

 

코드

class Solution {
 
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        return bs(arr, 0, 1, k);
    }
 
    // low~high 범위 내에서 k번째 분수를 구하는 메서드
    private int[] bs(int[] arr, double low, double high, int k) {
        while(low < high) {
            double mid = (low+high)/2;
 
            // 중간값보다 작거나 같은 분수의 개수 및 그 중 가장 큰 분수를 구함
            int[] smallerF = getSmallerFraction(arr, mid);
            int cnt = smallerF[0];
 
            if (cnt == k) {
                return new int[]{smallerF[1], smallerF[2]};
            }
            else if (cnt < k) {
                low = mid;
            } else {
                high = mid;
            }
 
        }
        return null;
    }
 
    private int[] getSmallerFraction(int[] arr, double num) {
        int cnt = 0;
        int maxT = 0, maxB = 1;
 
        int j = 0;
        for(int i=0; i<arr.length-1; i++) {
            int hereT = arr[i];
 
            // 분자(arr[i])를 고정하고 분모(arr[j])를 증가시키면서 
            // num보다 작거나 같은 최대 분모를 구함
            while (j < arr.length && hereT >= num * arr[j]) {
                j++;
            }
 
            // 현재 분자로 num보다 작은 경우가 없으면 종료
            if (j==arr.length) {
                break;
            }
 
            // 현재 분자로 num보다 작은 분모의 개수만큼 cnt 증가
            cnt += (arr.length-j);
 
            int hereB = arr[j];
 
            // 최대 분수 갱신
            if (j < arr.length && (hereT*maxB > maxT*hereB)) {
                maxT = hereT;
                maxB = hereB;
            }
        }
 
        return new int[]{cnt, maxT, maxB};
    }
}

• 시간복잡도: O(NlogN)
• 공간복잡도: O(1)

 

오늘의 학습 회고

•  

• 이분탐색을 떠올리고, 구성하는 흐름을 좀 더 연습해야겠다.