23.04.02. 풀었던 문제들

Leetcode 2300. Successful Pairs of Spells and Potions

 문제를 보고 binary search임을 깨달았다.

 일단 문제에서 주어지는 size n, size m의 배열이 있다. 이 배열의 모든 값을 곱하면 O(nm)으로, $10^{10}$으로 시간 초과가 난다. 다른 방법이 없을까?

 문제를 잘 살펴보면 어떤 potion의 값 p에 대해 어떤 값 x가 주어졌을 때 success를 만족하는지 안 하는지는 px가 success보다 크거나 같은지 여부로 쉽게 알 수 있다. 그러면 역으로 p가 주어졌을 때 success를 만족하는 x값을 역산할 수 있다. 만약 potion이 [1, 2, 3, 4, 5]에 success가 7이라면 success를 만족하는 x값은 [7, 4, 3, 2, 2]이다.

 따라서 어떤 spell 값 s가 이 x값들의 배열 중 s보다 더 작거나 같은 x값의 개수만 찾아주면 된다. 만약 x값 배열이 정렬되어 있다면 binary search로 쉽게 s값보다 작거나 같은, 즉 success를 만족하는 potion의 개수를 찾을 수 있다!

• potions를 순회하며 x값을 찾고, x값 배열을 정렬한다. ... 1
• 이후 spells를 순회하며 x값 배열에서 binary search, upper bound의 index를 찾아오면 된다. ... 2
  • x값 배열에서 spells 값 s의 upper bound가, s보다 작은 x들의 개수이다. 

 이걸 구현하면 된다.

 

// Runtime 242 ms Beats 76.16%
// Memory 100.4 MB Beats 12.14%

typedef long long ll;

class Solution {
public:
    int getUpperBoundIndex(vector<ll> &arr, ll target){
        int start = 0, end = arr.size(), mid;
        while(start < end){
            mid = (start + end)/2;
            if(arr[mid] > target){
                end = mid;
            }
            else start = mid+1;
        }
        return end;
    }
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        // 각 potion에 얼마만큼의 배율이 곱해져야 success가 되는지 배열
        // ... 1
        vector<ll> thresholds(potions.size());
        for(int i = 0; i<potions.size(); i++){
            thresholds[i] = success / potions[i] + (success % potions[i] != 0);
        }
        sort(thresholds.begin(), thresholds.end(), less<ll>());

        // ... 2
        vector<int> answer(spells.size());
        for(int i = 0; i<spells.size(); i++){
            answer[i] = getUpperBoundIndex(thresholds, (ll)spells[i]);
        }

        return answer;
    }
};

 

시간복잡도

 1번 단계에서 모든 potion을 순회하므로 O(m), 이후 potion을 정렬하므로 O(mlogm).

 2번 단계에서 모든 spells를 순회하며 각 탐색에서 m size 배열을 binary search하므로 O(nlogm)이다.

 따라서 O((n+m)logm)이다.

 

공간복잡도

 추가 배열로는 threshold 배열만 사용하므로 O(m)이다.