[리트코드][JAVA] 786. K-th-smallest-prime-fraction (K번째로 작은 소수 분수)

💡 문제
K-th-smallest-prime-fraction (https://leetcode.com/problems/k-th-smallest-prime-fraction/description/)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

---

🤓 문제 풀이

🔨 문제 설명

번역:

786. K번째로 작은 소수 분수

정렬된 정수 배열 arr이 주어지는데, 이 배열에는 1과 소수(prime number)들이 포함되어 있습니다. 배열의 모든 정수는 유일합니다. 또한 정수 k가 주어집니다.

0 <= i < j < arr.length인 모든 i와 j에 대해, 우리는 분수 arr[i] / arr[j]를 고려합니다.

k번째로 작은 분수를 반환하세요. 답변은 크기가 2인 정수 배열로 반환하며, answer[0] == arr[i] 그리고 answer[1] == arr[j] 입니다.

 

예제 1:

입력: arr = [1,2,3,5], k = 3

출력: [2,5]

설명: 고려해야 할 분수는 순서대로 다음과 같습니다: 1/5, 1/3, 2/5, 1/2, 3/5, 2/3. 세 번째로 작은 분수는 2/5입니다.

 

예제 2:

입력: arr = [1,7], k = 1

출력: [1,7]

제약사항:

• arr.length는 2 이상 1000 이하입니다.
• 1 <= arr[i] <= 3 * 10^4
• arr[0] == 1
• arr[i]는 i > 0일 때 소수입니다.
• arr의 모든 숫자는 유일하며 엄격히 증가하는 순서로 정렬됩니다.
• 1 <= k <= arr.length * (arr.length - 1) / 2

"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."

이 문장은 문제의 핵심 요구사항을 나타냅니다: 모든 가능한 분수 중 k번째로 작은 분수를 찾아야 한다는 것입니다. 여기서 중요한 포인트는 "모든 가능한 분수 중 k번째로 작은 것"을 찾아야 한다는 점입니다.

---

🔨 접근 방법

이 문제는 분수를 계산하고 정렬하여 k번째로 작은 분수를 찾는 것과 관련이 있습니다. 모든 가능한 분수를 나열한 후 이를 정렬하는 것이 일반적인 접근 방법일 수 있지만, 이 방식은 비효율적일 수 있습니다. 대신, 이진 탐색과 우선순위 큐를 사용하는 방식이 더 효율적일 수 있습니다.

• 이진 탐색:
  • 특정 값 x를 기준으로 분수들을 이진 탐색하며, arr[i] / arr[j] <= x인 분수의 개수를 세어 그 개수가 k와 같은지 확인합니다.
• 우선순위 큐:
  • 초기 분수들을 큐에 넣고, 가장 작은 분수를 꺼내면서 다음 가능한 분수를 큐에 넣는 과정을 반복합니다. k번째로 작은 분수를 찾을 때까지 이 과정을 진행합니다.

---

🔨 문제 풀이 과정

• 분수의 생성:
  • arr 배열에서 두 요소를 선택하여 가능한 모든 분수를 생성합니다.
  • 이때, 분수는 arr[i] / arr[j] 형태로 나타낼 수 있습니다.
• 분수의 정렬:
  • 생성된 분수들을 정렬합니다. 이는 각 분수를 비교하여 순서를 매기는 것입니다.
• k번째 분수 찾기:
  • 정렬된 분수 리스트에서 k번째 분수를 찾습니다.
  • 이때, k번째 분수는 arr[i] / arr[j] 형태의 값을 가집니다.

---

🔨 이진탐색 선택 이유

1. 모든 가능한 분수 고려해야 합니다. 문제에서는 0 <= i < j < arr.length 범위 내에서 가능한 모든 arr[i] / arr[j] 분수를 고려하라고 명시하고 있습니다. 이는 모든 가능한 분수를 생성하여 정렬한 다음 k번째로 작은 분수를 찾는 것과 동일합니다.
2. 효율적인 탐색이 필요합니다. 가능한 모든 분수를 생성하고 정렬하는 것은 비효율적일 수 있습니다. 배열의 길이가 최대 1000이므로 가능한 분수의 수는 최대 499500개가 될 수 있습니다. 단순히 모든 분수를 나열하고 정렬하는 방식은 시간이 많이 걸릴 수 있습니다.
3. 이진 탐색은 효율적으로 정답을 찾는 방법입니다. 여기서는 분수의 값을 기준으로 이진 탐색을 사용할 수 있습니다. 예를 들어, 특정 값 x를 기준으로 arr[i] / arr[j] <= x인 분수의 개수를 세어 k보다 작은지 큰지를 판단하는 방식입니다. 이는 문제의 "k번째로 작은 분수"를 찾는 효율적인 방법으로 문제를 해결할수있습니다.
4. 우선순위 큐를 사용하면 작은 값부터 차례대로 정렬된 분수를 효율적으로 관리할 수 있습니다. 각 단계에서 가장 작은 분수를 큐에서 꺼내고, 다음 가능한 분수를 큐에 추가하는 방식으로 k번째 분수를 찾을 수 있습니다. 우선순위 큐를 사용하여 k번째 분수를 찾기 위해 k번의 삽입과 삭제 연산을 수행하게 되므로 시간 복잡도를 줄여주고있습니다.

---

🔨 구현코드

1) 이진탐색 + 우선순위 큐

import java.util.PriorityQueue;

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        // 우선순위 큐를 사용하여 분수의 오름차순으로 정렬
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
            return arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]];
        });
        
        // 초기 분수들을 큐에 추가
        for (int j = 1; j < arr.length; j++) {
            pq.offer(new int[]{0, j});
        }
        
        // k번째 분수를 찾기 위해 k-1개의 분수를 큐에서 제거
        for (int i = 0; i < k - 1; i++) {
            int[] fraction = pq.poll();
            int i1 = fraction[0];
            int j1 = fraction[1];
            
            // 다음 가능한 분수를 큐에 추가
            if (i1 + 1 < j1) {
                pq.offer(new int[]{i1 + 1, j1});
            }
        }
        
        // k번째 분수를 반환
        int[] kthSmallestFraction = pq.poll();
        return new int[]{arr[kthSmallestFraction[0]], arr[kthSmallestFraction[1]]};
    }
}

 

2) 모든 가능한 분수를 나열한 후 이를 정렬하는 것이 일반적인 접근 방법

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        // 모든 가능한 분수를 저장할 리스트
        List<Fraction> fractions = new ArrayList<>();

        // 가능한 모든 분수를 리스트에 추가
        for (int i = 0; i < arr.length; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                fractions.add(new Fraction(arr[i], arr[j]));
            }
        }

        // 분수를 정렬
        Collections.sort(fractions);

        // k번째로 작은 분수를 반환
        Fraction kthFraction = fractions.get(k - 1);
        return new int[]{kthFraction.numerator, kthFraction.denominator};
    }
}

// 분수를 나타내는 클래스
class Fraction implements Comparable<Fraction> {
    int numerator;
    int denominator;
    double value;

    Fraction(int numerator, int denominator) {
        this.numerator = numerator;
        this.denominator = denominator;
        this.value = (double) numerator / denominator;
    }

    @Override
    public int compareTo(Fraction other) {
        return Double.compare(this.value, other.value);
    }
}

---

📚 풀이 보완

1) 코드 설명

• 우선순위 큐:
  • 분수를 오름차순으로 정렬하기 위해 우선순위 큐를 사용합니다.
  • 분수의 오름차순으로 정렬하여 가장 작은 분수부터 처리합니다.
  • arr[i] / arr[j] 형태의 분수를 arr[i] * arr[j2] - arr[j] * arr[i2] 비교
  • 큐의 요소는 분수의 인덱스 쌍 [i, j]로 저장됩니다.
• 초기 분수 추가:
  • j를 1부터 arr.length까지 반복하여 초기 분수들을 큐에 추가합니다. 이는 1/arr[j] 형태의 분수들입니다.
• 분수 탐색(k번째 분수 찾기):
  • k-1번 반복하여 큐에서 분수를 제거하고, 다음 가능한 분수를 큐에 추가합니다.
  • i + 1 < j 조건을 만족하는 경우 다음 가능한 분수를 큐에 추가합니다.
• 결과 반환:
  • k번째 분수를 찾아서 반환합니다. 이때, 분수는 [arr[i], arr[j]] 형태로 반환됩니다.

2) 코드 설명

1. Fraction 클래스:
   • numerator와 denominator로 분수를 표현합니다.
   • value 필드는 분수의 실제 값을 저장합니다.
   • Comparable<Fraction> 인터페이스를 구현하여 compareTo 메소드를 통해 분수의 값을 기준으로 정렬할 수 있습니다.
2. 모든 가능한 분수 생성:
   • 이중 for문을 사용하여 가능한 모든 분수를 생성합니다.
   • i < j 조건을 만족하는 모든 arr[i] / arr[j] 분수를 리스트에 추가합니다.
3. 분수 정렬:
   • Collections.sort(fractions)를 통해 분수 리스트를 정렬합니다. Fraction 클래스의 compareTo 메소드를 사용하여 분수의 값을 기준으로 정렬합니다.
4. k번째 분수 반환:
   • 정렬된 리스트에서 k번째로 작은 분수를 찾습니다.
   • 0-based index를 사용하기 때문에 k - 1번째 요소를 가져와 반환합니다.

이 코드는 가능한 모든 분수를 나열하고 정렬한 후 k번째로 작은 분수를 반환하는 단순한 접근 방법을 사용합니다. 이 방법은 이해하기 쉽지만, 큰 입력에 대해 비효율적일 수 있습니다. 따라서 더 큰 입력에 대해서는 앞서 설명한 이진 탐색과 우선순위 큐를 사용하는 방법이 더 적합합니다.

 

---

📍 Plus+

공간 복잡도

1. 우선순위 큐 (PriorityQueue): 이진 탐색을 통해 생성된 분수 후보군을 저장합니다. 우선순위 큐의 크기는 최악의 경우 $O(n)$이 될 수 있습니다.
2. 이진 탐색을 위한 보조 배열: 주어진 배열에서 생성된 모든 분수 후보군을 저장하고, 정렬된 상태를 유지합니다. 이 배열의 크기는 최악의 경우$O(n^2)$가 될 수 있습니다.

따라서 전체적인 공간 복잡도는 우선순위 큐와 보조 배열의 공간 복잡도의 합이 됩니다. 이는

$O(n + n^2) = O(n^2)$ 입니다.

시간복잡도

1. 이진 탐색을 통한 분수 생성: 주어진 배열에서 모든 가능한 분수를 생성하는 데 사용됩니다. 각 원소에 대해 다른 모든 원소를 대상으로 이진 탐색을 수행하므로 이 과정의 시간 복잡도는 $O(n \log n)$입니다.
2. 우선순위 큐에 삽입: 생성된 모든 분수 후보군을 우선순위 큐에 삽입하는 과정입니다. 각 삽입 연산의 시간 복잡도는 우선순위 큐의 내부 구현에 따라 다르지만, 일반적으로 $O(\log n)$입니다.
3. 우선순위 큐에서 k번째 분수 찾기: k번째 분수를 찾기 위해 우선순위 큐에서 k번 pop하는 과정입니다. 각 pop 연산의 시간 복잡도는 우선순위 큐의 내부 구현에 따라 다르지만, 일반적으로$O(\log n)$입니다.

따라서 전체적인 시간 복잡도는 이진 탐색을 통한 분수 생성에 의해 주도되며, 이는 $O(n \log n)$입니다.

요약

• 공간 복잡도 : $O(n^2)$
• 시간 복잡도 : O(n \log n)​

---

기본 개념을 정확하게 알고 지나가야한다. 주말에는 효율적인 알고리즘을 설계하기위한 기본 개념을 글로 정리해야겠다.