[leetcode] 2563. Count the Number of Fair Pairs #2

안녕하세요. 이번에는 전에 풀었던 leetcode에서 2563. Count the Number of Fair Pairs 문제를 다시 풀어보려고 합니다.

 

부족했던 실행 시간을 이번에 개선해보겠습니다!

5%라니...

• 참고: https://goodahn.tistory.com/246

 

1. 개선된 문제 풀이

아쉽게도 저는 더 나은 풀이 방법을 찾지 못해서 leetcode의 풀이를 참고했습니다.

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

 

저는 이전에 1) 수열을 오름차순으로 정렬하고, 2) binary search를 이용해서 모든 수에 대해 special 한 수의 개수를 찾았습니다.

 

하지만 더 좋은 방법이 있었습니다.

1) 수열을 오름차순으로 정렬하고, 2) two pointer 방식으로 special 한 수의 개수를 찾는 것입니다.

 

two pointer 방식을 간단하게 설명드리면 시작점을 가리키는 포인터와 끝점을 가리키는 포인터를 두고

조건에 따라서 각 포인터를 이동시키면서 원하는 값을 찾는 방식입니다.

 

여기서는 주어진 수보다 합이 작은 두 수 쌍의 개수를 찾을 때 사용합니다.

 

(upper+1보다 합이 작은 두 수 쌍의 개수 - lower 보다 합이 작은 두 수 쌍의 개수)  로 special한 수의 개수를 찾는 것이죠!

 

제가 생각해낸 방법은 아니지만 딱 적용하고 보니 효율이 무지막지하게 상승했습니다 ㄷㄷ

99%라니!!!

 

 

+ 코드

class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        sorted_nums = sorted(nums)
        return find_num_of_pair_less_than(sorted_nums, upper+1) - find_num_of_pair_less_than(sorted_nums, lower)
        
def find_num_of_pair_less_than(nums: List[int], target: int) -> int:
    result = 0
    left, right = 0, len(nums)-1
    while left < right:
        if nums[left] + nums[right] < target:
            result += right - left
            left += 1
        else:
            right -= 1
    return result