2563. Count the Number of Fair Pairs

Problem : https://leetcode.com/problems/count-the-number-of-fair-pairs

Difficulty : Medium

Status : Solved

Time : ??:??:??

---

---

풀이

모바일로 풀어 보는 경우를 생각해서 탬플릿을 단순화해야할까? 싶다.

각설하고, 처음 접근법은 binary search로 풀어보자고 생각했다. lower bound와 upper bound는 O(logN)시간복잡도로 구할 수 있고, 하나의 인자를 고정한 체로 다른 인자에 대해 lower bound와 upper bound를 구할 수 있기 때문이다. 이를테면, lower <= nums[i] + nums[j] <= upper인 경우 nums[i]를 고정시키면 lower - nums[i] <= nums[j] <= upper - nums[i]거 되고, 이는 nums[j]를 구하는 문제로 변모한다.

풀이코드는 다음과 같다.

class Solution:
    def binarySearch(self, mode, target) :
        start, end = 0, len(self.nums)
        while start < end :
            mid = (start + end) // 2
            if self.nums[mid] > target and mode or self.nums[mid] >= target and not mode:
                end = mid
            else :
                start = mid + 1
        return end
                
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        self.nums = sorted(nums)
        result = 0
        for i, n in enumerate(self.nums) :
            right = self.binarySearch(True, upper - n)
            left = self.binarySearch(False, lower - n)
            if left <= i < right :
                right -= 1
            result += right - left
                
        return result // 2
        

문제는 binary search 이전에 정렬을 수행해야 하고, 둘 모두 동일한 시간복잡도O(NlogN)이 소요될 것이다. 정렬만 수행하되, 우리가 원하는 fair를 더 빠르게 찾는 법이 있을 것이다. 대표적으로는 투 포인터를 이용한 방법 등이 존재한다.