BOJ_3151_합0

걸린 시간 : 20m

알고리즘 분류: 투포인터, 이분탐색

접근 방식

문제를 봤을때 누가봐도 이분탐색을 해야하는 문제라고 판단할 것 같습니다. 하지만 투 포인터를 사용하고 한 수를 어떻게 찾아가느냐에서 분기점이 나뉘어질 것 같은데 저는 이분탐색을 활용하여 가능한 모든 수를 찾는 방식을 선택하였습니다. 하지만 중복된 수를 포함할 수 있기 때문에 이분탐색의 upper bound, lower bound를 고려해야만 모든 경우의 수를 탐색할 수 있었습니다. 다만, Java에서는 상계, 하계를 지원하지 않기때문에 이분탐색을 직접 구현하여 메서드를 분리하여 구현하였습니다.

package BOJ_3151_합0;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] nums = new int[N];

        for (int i = 0; i < N; i++) {
            nums[i] = sc.nextInt();
        }

        Arrays.sort(nums);
        long count = 0;

        for (int i = 0; i < N - 2; i++) {
            for (int j = i + 1; j < N - 1; j++) {
                int target = -(nums[i] + nums[j]);
                int lower = lowerBound(nums, j + 1, N, target);
                int upper = upperBound(nums, j + 1, N, target);
                count += (upper - lower);
            }
        }

        System.out.println(count);
    }

    static int lowerBound(int[] arr, int left, int right, int target) {
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }

    static int upperBound(int[] arr, int left, int right, int target) {
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}