[LeetCode] 2300. Successful Pairs of Spells and Potions - Java

https://leetcode.com/problems/successful-pairs-of-spells-and-potions/description/

Successful Pairs of Spells and Potions - LeetCode

---

문제

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가 주어질 때 spells의 i번째 요소와 potions배열의 값의 곱이 success 이상이 되는 개수를 구하여 배열로 return 하는 문제이다.

이분 탐색을 이용하여 풀이한다.

우선 이분탐색을 이용하기 위해 potions 배열을 오름차순으로 정렬한다.

// potions 배열 오름차순으로 정렬
Arrays.sort(potions);

 

spells 배열의 모든 요소를 탐색하며 이분탐색을 실행하고 spells[i]의 값과 potions 배열의 각 요소의 곱이 success 이상이 되는 개수를 구하여 spells 배열에 업데이트한다.
spells배열의 모든 요소의 탐색이 끝나면 spells 배열을 return한다.

// spells 배열의 모든 요소 탐색
for(int i = 0; i < spells.length; i++) {
    // 이진 탐색으로 개수를 구하여 spells 배열에 값 업데이트
    spells[i] = binarySearch(spells[i], potions, success);
}

// 업데이트된 spells 배열을 return
return spells;

 

이분탐색에 사용하는 함수는 다음과 같다.
현재 탐색중인 spells 배열의 요소와 potions 배열, 그리고 구하고자 하는 값의 기준이 되는 target 변수를 인자로 받는다.

// 이분 탐색
public int binarySearch(int spell, int[] potions, long target) {

}

 

정렬된 potions 배열의 마지막 요소와 spell의 곱이 target보다 작은 경우 조건을 만족하는 경우가 없으므로 바로 0을 return한다.

// 정렬된 potions 배열의 마지막 요소와 spell의 곱이 target보다 작은 경우 0을 return
if((long)potions[potions.length - 1] * spell < target) return 0;

 

반대로 정렬된 potions 배열의 첫번째 요소와 spell의 곱이 target 이상인 경우 모든 요소가 조건을 만족하므로 potions 배열 길이를 return 한다.

// 정렬된 potions 배열의 첫번째 요소와 spell의 곱이 target 이상인 경우 potions 배열 길이를 return
if((long)potions[0] * spell >= target) return potions.length;

 

그리고 이분탐색에 사용할 변수들을 선언한다.

// target 이상이 되는 potions 요소의 개수
int result = 0;
// 시작지점 인덱스
int start = 0;
// 종료지점 인덱스
int end = potions.length - 1;
// 중간지점 인덱스
int mid;

 

중간지점의 인덱스를 계산하고 세 가지 경우로 나누어 탐색한다.

1. potions의 중간지점의 값과 spell의 곱이 target보다 크거나 같고, potions의 중간지점의 이전 값과 spell의 곱이 target보다 작은 경우

이 경우 중간지점이 문제에서 제시하는 조건을 만족하는 가장 작은값을 가진 지점이므로 중간 지점부터 배열의 끝까지의 길이를 결과값에 담고 탐색을 종료한다.

2. potions의 중간지점의 값과 spell의 곱이 target보다 작은 경우

두 번째 경우에는 문제에서 제시한 조건에 도달하기 위해서는 아직 중간지점 뒤로 이동하여야하므로 시작지점을 중간지점의 뒤로 이동한다.

3. 나머지 경우

나머지 경우에는 현재 문제에서 제시한 조건에는 도달하였지만 중간 이전 지점에도 조건을 만족하는 값들이 존재하므로 종료 지점을 중간지점 앞으로 이동한다.

위의 세가지 조건을 시작지점이 종료지점보다 커질 때까지 반복하여 탐색한다.

탐색이 종료될 때까지 조건을 만족하는 지점을 찾지 못한경우 0을 return

// 시작지점과 종료지점이 교차할 때 까지 반복
while(start <= end) {
    // 중간지점 인덱스 계산
    mid = (start + end) / 2;

    // potions의 중간지점의 값과 spell의 곱이 target보다 크거나 같고
    // potions의 중간지점의 이전 값과 spell의 곱이 target보다 작은 경우
    // 중간 지점부터 끝까지의 값을 result에 저장하고 탐색 종료
    if((long)potions[mid] * spell >= target && (long)potions[mid - 1] * spell < target) {
        result = potions.length - mid;
        break;
    }
    // potions의 중간지점의 값과 spell의 곱이 target보다 작은 경우
    // 시작지점을 중간지점 뒤로 설정
    else if((long)potions[mid] * spell < target) {
        start = mid + 1;
    }
    // 나머지 경우 종료지점을 중간지점 앞으로 설정
    else {
        end = mid - 1;
    }
}

return 0;

---

최종 코드

class Solution {
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        // potions 배열 오름차순으로 정렬
        Arrays.sort(potions);
        
        // spells 배열의 모든 요소 탐색
        for(int i = 0; i < spells.length; i++) {
            // 이진 탐색으로 개수를 구하여 spells 배열에 값 업데이트
            spells[i] = binarySearch(spells[i], potions, success);
        }

        // 업데이트된 spells 배열을 return
        return spells;
    }

    // 이분 탐색
    public int binarySearch(int spell, int[] potions, long target) {
        // 정렬된 potions 배열의 마지막 요소와 spell의 곱이 target보다 작은 경우 0을 return
        if((long)potions[potions.length - 1] * spell < target) return 0;
        // 정렬된 potions 배열의 첫번째 요소와 spell의 곱이 target 이상인 경우 potions 배열 길이를 return
        if((long)potions[0] * spell >= target) return potions.length;

        // target 이상이 되는 potions 요소의 개수
        int result = 0;
        // 시작지점 인덱스
        int start = 0;
        // 종료지점 인덱스
        int end = potions.length - 1;
        // 중간지점 인덱스
        int mid;
        
        // 시작지점과 종료지점이 교차할 때 까지 반복
        while(start <= end) {
            // 중간지점 인덱스 계산
            mid = (start + end) / 2;
            
            // potions의 중간지점의 값과 spell의 곱이 target보다 크거나 같고
            // potions의 중간지점의 이전 값과 spell의 곱이 target보다 작은 경우
            // 중간 지점부터 끝까지의 값을 return
            if((long)potions[mid] * spell >= target && (long)potions[mid - 1] * spell < target) {
                return potions.length - mid;
            }
            // potions의 중간지점의 값과 spell의 곱이 target보다 작은 경우
            // 시작지점을 중간지점 뒤로 설정
            else if((long)potions[mid] * spell < target) {
                start = mid + 1;
            }
            // 나머지 경우 종료지점을 중간지점 앞으로 설정
            else {
                end = mid - 1;
            }
        }
        
        return 0;
    }
}

---