2300. Successful Pairs of Spells and Potions (이진 탐색)

제약:

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

<아이디어>

long 타입의 success를 비교하는 방법은 (long)spell*potion >= success 타입 캐스팅을 통해 해결이 가능하다.

문제점은 단순 이중 for문을 통해 해결 하려할 경우 제한 시간 초과가 나오기 때문에

선형 탐색보다 더 빠른 이분 탐색을 사용 할 필요가 있었다. 

여기서 우리가 배열에서 찾아야 할 건 주어진 비교식에 처음으로 성립하는 값이다.

 

<정답 코드>

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    // 시간 복잡도 O(nlog m) 공간 복잡도 O(1)
    public int[] successfulPairs(int[] spells, int[] potions, long success) {
        List<Integer> ans = new ArrayList<>();
        int m = potions.length;
        Arrays.sort(potions);
        for (int spell : spells) {
            int left = 0;
            int right = m-1;
            // 이분 탐색 변형
            while(left<=right){
                // System.out.println(left+", "+right);
                int mid = left+(right-left)/2;
                long tmp = (long)spell*potions[mid];
                // 종료 조건을 넣지 않는 이유는 배열에서 주어진 비교식에 처음으로 성립하는 값을 찾기 위해서다.
                // 찾는 값이 mid의 해당하는 값보다 작거나 같다면 탐색 범위의 오른쪽의 범위를 좁힌다.
                if(tmp>=success)
                    right = mid-1;
                // 찾는 값이 mid의 해당하는 값보다 크다면 탐색 범위의 오른쪽의 범위를 좁힌다.
                else
                    left = mid+1;
            }
            ans.add(m-left);
        }
        // 리스트 보다는 일반 배열을 사용하는걸 권장한다.
        return ans.stream().mapToInt(i->i).toArray();
    }
}