[코테연습] 2563. Count the Number of Fair Pairs

배열 / 이진탐색 / 투포인터 문제

문제분석

• 목표: 배열 nums에서 두 수의 합이 주어진 범위 [lower, upper]에 포함되는 쌍의 개수를 구하는 문제.
• 조건:
  • 주어진 배열 nums에서 인덱스 i와 j에 대해 i < j이어야 함.
  • 합이 lower <= nums[i] + nums[j] <= upper 범위에 포함되는 경우만 유효한 쌍으로 간주.
• 문제점:
  • 배열의 크기가 최대 10^5이므로 모든 쌍을 직접 탐색하는 O(n^2) 방식은 비효율적임.
  • 효율성을 높이기 위해 투 포인터와 이분 탐색을 활용할 필요가 있음.

문제풀이

• 1단계: 배열 정렬
  • nums 배열을 정렬하여 이후 탐색 과정을 단순화함.
• 2단계: 투 포인터와 이분 탐색을 사용한 범위 탐색
  • 각 nums[left]에 대해 이분 탐색으로 두 개의 인덱스를 찾음:
    • lower_bound: nums[left] + nums[right] >= lower를 만족하는 right의 최소 인덱스.
    • upper_bound: nums[left] + nums[right] <= upper를 만족하는 right의 최대 인덱스.
  • 두 인덱스 사이의 값들이 모두 조건을 만족하므로, (upper_bound - lower_bound + 1)을 통해 쌍의 개수를 누적하여 구함.

 

> java

 

public class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums);  // 배열 정렬
        long count = 0;

        for (int left = 0; left < nums.length - 1; left++) {
            // lower bound 탐색: nums[left] + nums[right] >= lower가 되는 최소 right
            int start = lowerBound(nums, left + 1, nums.length - 1, lower - nums[left]);

            // upper bound 탐색: nums[left] + nums[right] <= upper가 되는 최대 right
            int end = upperBound(nums, left + 1, nums.length - 1, upper - nums[left]);

            // 유효한 범위가 있으면 카운트 추가
            if (start <= end) {
                count += (end - start + 1);
            }
        }
        return count;
    }

    // lower bound 함수: nums[left] + nums[right] >= lower를 만족하는 첫 인덱스를 찾습니다.
    private int lowerBound(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] >= target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    // upper bound 함수: nums[left] + nums[right] <= upper를 만족하는 마지막 인덱스를 찾습니다.
    private int upperBound(int[] nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
}

 

 

> python

 

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        n = len(nums)
        count = 0

        for index in range(n-1) :
            start = self.lower_bound(nums, index+1, n-1, lower - nums[index])
            end = self.upper_bound(nums, index+1, n-1, upper - nums[index])

            if start <= end :
                count += (end-start+1)

        return count

    def lower_bound(self, nums, left, right, target) :
        while left <= right :
            mid = left + (right - left) // 2
            if nums[mid] >= target :
                right = mid - 1
            else :
                left = mid + 1
        return left

    def upper_bound(self, nums, left, right, target) :
        while left <= right :
            mid = left + (right - left) // 2
            if nums[mid] <= target :
                left = mid + 1
            else :
                right = mid - 1
        return right