[python3] 2300. Successful Pairs of Spells and Potions

풀이 일자: 23.04.02

난이도: [Medium]

분류: [Array, Two Pointers, Binary Search, Sorting]

문제 내용

문제의 내용은 정수가 담긴 2개의 배열이 주어지고 이 배열들 간의 이루어질 수 있는 원소들간의 곱이 success라고 하는 기준점 이상인 경우를 count해서 spells 기준으로 가능한 경우의 수를 리턴하는 문제이다.

spells = [5,1,3], potions= [1,2,3,4,5], success = 7

spells = 5 => [5,10,15,20,25]  # successful 횟수는 4
spells = 1 => [1,2,3,4,5]      # successful 횟수는 0
spells = 3 => [3,6,9,12,15]    # successful 횟수는 3

# answer = [4,0,3]

문제 해결 흐름

1. 처음에는 Brute-force한 방식으로 해보자.

→ 그냥 spells와 potions 두 배열을 동시에 순회하면 TLE가 나온다.

 

2. 그럼 DP인가? 뭔가 memorization으로 해서 풀어도 괜찮지 않을까?

→ 너무 과하다. 또한 한 배열의 크기가 10^5이기도 하고 DP로 풀어봤자 TLE가 나올 것이며 DP에도 적합하지 않다.

 

3. 고민 끝에 category를 봤는데 Binary Search가 있었다.

→ leetcode에 binary search문제가 한동안 나오지 않아 바로 떠올리지 못했다.

 

4. binary search를 위해 정렬된 배열이 필요한데 그 대상은 potions이 적합하겠다.

→ spells마저 정렬하면 그 위치에 대해서는 기록을 해두어야 한다. ( 결과를 spells 순서대로 가능한 경우의 수를 구해야하므로)

 

5.potions를 정렬해서 binary Search하는 기준을 정하자

→ spells * potions ≥ success의 관계를 만족해야 하므로 potions ≥ ceil( spells/success)을 만족하는 potions의 위치를 찾으면 되겠다.

→ 일반적인 binary search 알고리즘을 작성해도 괜찮고 bisect.bisect_left를 사용하면 만약에 해당 원소가 배열에 없다면 있어야 하는 위치가 결과로 나온다.

 

6. 그러면 그 index기준으로 그 뒤에 있는 원소들은 다 되는거네..

→ ans[i] = m - Idx    // i번째 spells로 successful이 되는 경우의 수 =  potions의 전체 길이 - 위의 관계식을 만족하기 시작하는 idx

→ idx가 m과 같다면 만족하는 potion이 없다는 의미므로 0을 넣어야 한다.  

 

class Solution:
    def successfulPairs(self, spells: List[int], potions: List[int], success: int) -> List[int]:
        n,m = len(spells), len(potions);
        ans = [0] * n;

        potions.sort();

        for i in range(n):
            pos = bisect.bisect_left(potions, ceil(success/spells[i]));
            ans[i] = (m - pos) if pos < m else 0;
        
        return ans;

Time Complexity:  O(NlogM)

spells 배열의 순회와 내부적으로는 potions에 대한 이진탐색이 있었기에 NlogM의 시간복잡도를 가질 것이다.

 

Space Complexity: O(N)

결과로 spells의 크기의 배열을 만들어서 리턴해야하기 때문에 N의 공간복잡도를 가질 것이다.

 

다른 해결 방식

Official Solution에서는 나와 같은 방식으로 한 번 풀고 Two pointer를 이용하여 풀었는데 굳이 그렇게까지 풀어야 하나라는 생각했다. 다른 사용자들의 풀이또한 나와 같았다.

 

문제 링크

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

Successful Pairs of Spells and Potions - LeetCode