- Problem

2300. Successful Pairs of Spells and Potions

어떤 결과를 반환해야 하는지 이해하는데는 어렵지 않다.

- 내 풀이 1 (Brute-force, TLE)

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        pairs = []

        for spell in spells:
            pairs.append(sum(spell * potion >= success for potion in potions))
        
        return pairs

• 시간 복잡도: O(N*M)
  - N: spells.length
  - M: potions.length

• 공간 복잡도: O(N)

역시나 미디엄 난이도답게 완전 탐색으로 접근하면 시간 초과가 난다.
어떤 부분의 로직을 개선해서 효율성을 늘릴 수 있는지 조금 더 고민해봐야 한다.

- 내 풀이 2 (이분 탐색)

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        pairs = []
        potions.sort()

        for spell in spells:
            left, right = 0, len(potions) - 1
            
            while left <= right:
                mid = (left + right) // 2
                if potions[mid] * spell < success:
                    left = mid + 1
                else:
                    right = mid - 1
            
            pairs.append(len(potions) - left)
        
        return pairs

potions을 정렬하여 이분 탐색을 이용한다면 보다 빠르게 결과를 낼 수 있다.

- 결과

• 시간 복잡도: O(MlogM + NlogM)
  - MlogM -> Sorting
  - NlogM -> main loop

• 공간 복잡도: O(N)