[LeetCode] 786. K-th Smallest Prime Fraction

1. 문제 설명

786. K-th Smallest Prime Fraction

숫자 1과 소수(Prime number)들로 구성된 오름차순 정렬 배열 arr가 주어집니다.
배열 내의 두 수 arr[i]와 arr[j] (0 <= i < j < arr.length)로 만들 수 있는 분수 arr[i] / arr[j] 중 k번째로 작은 분수를 구하는 문제입니다.

• 입력: arr (정수 배열), k (정수)
• 출력: [arr[i], arr[j]] 형태의 크기 2짜리 배열

2. 접근 방식

1. 배열 내의 가능한 모든 분수 조합 (arr[i], arr[j])를 2중 반복문을 통해 생성합니다.
2. 생성된 모든 분수들을 실수 값(arr[i] / arr[j]) 기준으로 오름차순 정렬합니다.
3. 정렬된 배열에서 k - 1번째 인덱스의 분수 조각 [numerator, denominator]를 반환합니다.

3. 코드 구현 (TypeScript)

function kthSmallestPrimeFraction(arr: number[], k: number): number[] {
    const n = arr.length;
    const fraction: [number, number][] = [];

    // 모든 분수 조합 생성
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            fraction.push([arr[i], arr[j]]);
        }
    }

    // 분수값 기준 오름차순 정렬
    const sorted = fraction.toSorted(([aNume, aDeno], [bNume, bDeno]) => {
        const aVal = aNume / aDeno;
        const bVal = bNume / bDeno;
        return aVal - bVal;
    });

    // k번째로 작은 분수 반환
    return sorted[k - 1];
}