leetcode link

You are given two positive integer arrays spells and potions, of length n and m respectively, where spells[i] represents the strength of the ith spell and potions[j] represents the strength of the jth potion.

You are also given an integer success. A spell and potion pair is considered successful if the product of their strengths is at least success.

Return an integer array pairs of length n where pairs[i] is the number of potions that will form a successful pair with the ith spell.

Example 1:
Input: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
Output: [4,0,3]
Explanation:

• 0th spell: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4 pairs are successful.
• 1st spell: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0 pairs are successful.
• 2nd spell: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3 pairs are successful.
  Thus, [4,0,3] is returned.

Example 2:
Input: spells = [3,1,2], potions = [8,5,8], success = 16
Output: [2,0,2]
Explanation:

• 0th spell: 3 * [8,5,8] = [24,15,24]. 2 pairs are successful.
• 1st spell: 1 * [8,5,8] = [8,5,8]. 0 pairs are successful.
• 2nd spell: 2 * [8,5,8] = [16,10,16]. 2 pairs are successful.
  Thus, [2,0,2] is returned.

Constraints:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 105
• 1 <= spells[i], potions[i] <= 105
• 1 <= success <= 1010

---

두 양수 배열 spells와 potions이 주어지며, 각각의 길이는 n과 m입니다. 여기서 spells[i]는 i번째 주문의 강도를 나타내고 potions[j]는 j번째 포션의 강도를 나타냅니다.

정수 success도 주어집니다. 주문과 포션 쌍은 그들의 강도의 곱이 success 이상일 때 성공으로 간주됩니다.

길이가 n인 정수 배열 pairs를 반환합니다. 여기서 pairs[i]는 i번째 주문과 성공적인 쌍을 이룰 수 있는 모든 포션의 수입니다.

예제 1:
입력: spells = [5,1,3], potions = [1,2,3,4,5], success = 7
출력: [4,0,3]
설명:

• 0번 주문: 5 * [1,2,3,4,5] = [5,10,15,20,25]. 4쌍이 성공적입니다.
• 1번 주문: 1 * [1,2,3,4,5] = [1,2,3,4,5]. 0쌍이 성공적입니다.
• 2번 주문: 3 * [1,2,3,4,5] = [3,6,9,12,15]. 3쌍이 성공적입니다.
  따라서, [4,0,3]이 반환됩니다.

예제 2:
입력: spells = [3,1,2], potions = [8,5,8], success = 16
출력: [2,0,2]
설명:

• 0번 주문: 3 * [8,5,8] = [24,15,24]. 2쌍이 성공적입니다.
• 1번 주문: 1 * [8,5,8] = [8,5,8]. 0쌍이 성공적입니다.
• 2번 주문: 2 * [8,5,8] = [16,10,16]. 2쌍이 성공적입니다.
  따라서, [2,0,2]가 반환됩니다.

제약 사항:

• n == spells.length
• m == potions.length
• 1 <= n, m <= 105
• 1 <= spells[i], potions[i] <= 105
• 1 <= success <= 1010

Solution

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        Arrays.sort(potions); // 포션 배열을 정렬합니다.
        int[] result = new int[spells.length]; // 각 주문별 결과를 저장할 배열입니다.

        for (int i = 0; i < spells.length; i++) {
            int low = 0;
            int high = potions.length - 1;
            while (low <= high) {
                int mid = low + (high - low) / 2;
                if ((long) spells[i] * potions[mid] >= success) {
                    // 성공 조건을 만족하면 왼쪽 반을 더 탐색합니다.
                    high = mid - 1;
                } else {
                    // 성공 조건을 만족하지 않으면 오른쪽 반을 더 탐색합니다.
                    low = mid + 1;
                }
            }
            // 성공적인 쌍의 수를 계산하여 결과 배열에 저장합니다.
            result[i] = potions.length - low; // low는 success 조건을 만족하는 첫 인덱스입니다.
        }
        return result;
    }
}