[Binary Search][Medium] 2300. Successful Pairs of Spells and Potions

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

Successful Pairs of Spells and Potions - LeetCode

 

Q. 주어진 vector spells과 potions가 있을때, 두 원소의 곱이 sucess 값 이상이면 성공했다고 한다. 

이때 성공하게 되는 수를 vector로 반환하라. 

 

Solution. 

 두 벡터의 원소 값의 곱이 target수, 즉 sucess보다 크거나 같은 횟수를 반환하는 문제. 

 다만 그대로 하게 되면 O(NxN)의 TC가 소요되므로, 더 좋은 알고리즘이 있으면 그걸 선택하면 된다. 

 이런 경우 많이 사용케 되는 것이 Binary Search인데, 이 탐색을 위해서는 대상이 반드시 정렬되어 있어야 한다. 

 따라서 대상을 정렬하고, 그때부터는 해당 array에서 원하는 값이 되는 지점을 찾는 문제이다. 

 

 다만, 특정 값을 탐색하는 것이 아니고, 특정 값 이상되는 지점을 찾아서 반환하는 것은 조금 고민이 필요할 수 있겠다. 

 

int pairs_helper(vector<int>& vBuff, int left, int right, long long target)
{
    // 엇갈리는 지점의 left값이 목표값과 같거나 커지게 되는 첫 지점이다. 
    if (left > right) 
        return vBuff.size()-left;

    int mid = left + (right - left) / 2;
    // 중복값을 포함해서 목표값보다 크거나 같으면, 그 첫지점을 찾고자 왼쪽을 검색한다.
    if(vBuff[mid] >= target)
        return pairs_helper(vBuff, left, mid - 1, target);
    else   
        return pairs_helper(vBuff, mid + 1, right, target);
}

vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) 
{
	// binary search를 하고자, 우선 대상을 정렬한다.
    sort(potions.begin(), potions.end());

    vector<int> vRet;
    for (int k = 0; k < spells.size(); ++k)
    {
        long div = (success % spells[k]) == 0 ? success / spells[k] : 1 + (success / spells[k]);
        vRet.push_back(pairs_helper(potions, 0, potions.size() - 1, div ));
    }
    return vRet;
}

 

 

TC : O(logNxN)