[리트코드] 2563

작성일: 2024-11-13

플랫폼 : https://leetcode.com/

문제 링크 : https://leetcode.com/problems/count-the-number-of-fair-pairs?source=submission-noac

접근 방식

이분탐색과 투포인터를 활용한 방법으로 해결 할 수 있다.

정렬된 배열에서 시작점을 처음으로 잡는다. 이분탐색을 통해 시작점과 끝점을 구한다.
둘의 차를 통해 가능한 조합을 결과에 더한다.

이 과정에서 이분탐색이 핵심이다. 배열의 길이가 최대 10만이기에 완전탐색을 하면 시간복잡도가 O(n^2)이기에 시간초과가 발생한다.

결과

소스 코드

import java.util.*;
class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        Arrays.sort(nums); // 오름차순 정렬
        long answer = 0;
        for(int i=0; i<nums.length; i++){
            int a = search(nums, lower-nums[i], i+1);
            int b = search(nums, upper-nums[i]+1, i+1);
            answer+= b-a;
        }
        return answer;
    }

    int search(int[] nums, int target, int left){
        int right = nums.length;
        while(left<right){
            int mid = (left+right)/2;
            if(nums[mid]<target){
                left=mid+1;
            }else{
                right = mid;
            }
        }
        return left;
    }
}

다른 접근 방식

없음.

느낀 점

잊고 있었던 이분탐색을 다시 복습할 수 있어서 좋았다.