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

2300. Successful Pairs of Spells and Potions

 

https://youtu.be/OKnm5oyAhWg?si=k_d-0f6Nt10xOCD6

 

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        # spell * potion >= success 를 만족하는 쌍을 찾아야 함
        # 이를 변형하면: potion >= success / spell 이 됨
        # 즉, potion의 값이 특정 기준값 이상인 경우를 찾아야 함.

        # 1. potions 리스트를 정렬하여 이진 탐색을 수행 가능하도록 준비
        potions.sort()

        res = []  # 결과를 저장할 리스트

        # 2. 각 spell에 대해 적합한 potion 쌍의 개수를 찾음
        for s in spells:
            # **현재 spell에 대해 적합한 potion을 찾기 위해 이진 탐색**
            
            """
            # idx 의 역할:
            # 1) find weakest potion taht works (가장 왼쪽)
            #    success=10, spells=5, potions=[1,2,2,2,2,2,2,4] 라면, 
            #    가장 왼쪽 2의 index를 찾아야 함
            # 
            # 2) idx 의 초기값 중요. 
            #    바너리써치에서 해당하지 않으면,idx 값 갱신되지 않으므로, 
            #    len(potions) - idx = 0 이 되게, idx의 초기값을 정해야 함
            """
            idx = len(potions)  # 적합한 potion의 시작 인덱스 (기본값은 리스트의 길이)

            l, r = 0, len(potions) - 1  # 이진 탐색 범위 설정

            while l <= r:
                # 중간값 계산 (정수 나눗셈)
                m = (r + l) // 2
                
                # 현재 spell과 potion[m]의 곱이 success 이상인지 확인
                if s * potions[m] >= success:
                    r = m - 1  # 조건을 만족하므로 왼쪽으로 범위 좁힘
                    idx = m    # 현재 potion[m]이 조건을 만족하는 가장 왼쪽 값일 수 있음
                else:
                    l = m + 1  # 조건을 만족하지 않으므로 오른쪽으로 범위 좁힘

            # 조건을 만족하는 potion의 개수를 계산:
            # 전체 potions의 길이에서 적합한 시작 인덱스(idx)를 빼줌
            res.append(len(potions) - idx)

        return res  # 모든 spell에 대한 결과 반환