[LeetCode] 2563. Count the Number of Fair Pairs

https://leetcode.com/problems/count-the-number-of-fair-pairs/description/?envType=daily-question&envId=2024-11-13

leetcode - Count the Number of Fair Pairs

문제 유형: 정렬, 이진탐색, 투 포인터

문제 난이도: Medium

 

문제

Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

• 0 <= i < j < n, and
• lower <= nums[i] + nums[j] <= upper

n짜리 크기의 0-indexed의 배열 nums와 두 정수 lower와 upper가 주어집니다.

fair한 pair들의 개수를 구하시오.

 

pair (i, j)는 fair하기 위해, 0 <= i < j < n이고, lower <= nums[i] + nums[j] <= upper 여야 합니다.

 

풀이

우선, 배열을 정렬해준다.

배열을 정렬해도 되는 이유는, i, j의 의미가 그저 상이한 인덱스를 골라서 페어를 만들면 된다는 의미이기 때문이다.

 

그리고, 이진탐색을 사용할 것이다.

정렬된 배열에서 두 개의 인덱스를 찾을 것이다.

우선 둘 다 i보다 커야 하고, 

하나는 nums[i]와 합해져서 lower를 겨우 넘는 nums[lb]가 되어야 하고,

다른 하나는, nums[i]와 합해져서 upper이내로 들어오는 nums[rb]가 되어야 한다.

그러고, lb <= rb관계이면, i기준, i와 짝지을 수 있는 인덱스는 rb - lb + 1개이다.

lb와 rb를 각각 lower_bound()와 upper_bound() -1로 구한다.

 

i로 순차적으로 배열을 순회하면서 가능한 쌍들의 개수를 누적해주면 된다.

i입장에서 작지 않은 수들과 쌍을 매번 만드는 것이다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        long long ans = 0;

        for(int i = 0; i < n; ++i) {
            int t1 = lower - nums[i];
            int t2 = upper - nums[i];

            int lb = lower_bound(nums.begin()+i + 1, nums.end(), t1) - nums.begin();
            int rb = upper_bound(nums.begin()+i + 1, nums.end(), t2) - nums.begin() - 1;
            
            if(lb <= rb) ans += rb - lb + 1;
        }

        return ans;
    }
};