[2024] day 132. Leetcode 786. K-th Smallest Prime Fraction

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 10일 (금)
Leetcode daily problem

786. K-th Smallest Prime Fraction

https://leetcode.com/problems/k-th-smallest-prime-fraction/?envType=daily-question&envId=2024-05-10

Problem

고유한 1과 소수를 포함하는 정렬된 정수 배열 arr이 주어질 때,

0 <= i < j < arr.length인 모든 i와 j에 대해 분수 arr[i] / arr[j]를 고려해서 k번째로 작은 분수를 반환한다.

반환해야 하는 답변의 형태는 크기 2의 정수 배열로 ans[0] == arr[i], ans[1] == arr[j]이다.

Solution

binary search

주어진 소수 배열에서 k번째로 작은 소수 분수를 찾아 반환한다.
주어진 배열은 정렬되어 있지 않아서 배열에서 최대값을 찾아야 하는데, 여기서의 최소값은 0/1, 최대값은 1/1이다.

다음으로 이진 탐색을 사용해서 최소값과 최대값 사이에서 소수 분수를 찾는데, 각 이진 탐색에서 중간값을 구한 후에 배열 내에서 중간값보다 작은 소수 분수의 개수를 찾는다. 이를 위해서 이중 루프를 사용해 배열 내에서 현재 중간값보다 작은 소수 분수를 모두 센다.

그럼 다음 중간값보다 작은 소수 분수의 개수가 k보다 작으면, 중간값을 새로운 값으로 설정하고 그렇지 않으면 중간값을 새로운 최대값으로 설정한다.
이 과정을 반복해서 k번째로 작은 소수 분수를 찾을 수 있다.

Code

Complexicity

시간 복잡도

공간 복잡도