[백준] 7453. 합이 0인 네 정수

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {

    static int lowerBound(int[] a, int num) {
        int lt = 0, rt = a.length;
        while (lt < rt) {
            int mid = (lt + rt) / 2;
            if (a[mid] >= num)
                rt = mid;
            else lt = mid + 1;
        }
        return lt;
    }

    static int upperBound(int[] a, int num) {
        int lt = 0, rt = a.length;
        while (lt < rt) {
            int mid = (lt + rt) / 2;
            if (a[mid] > num)
                rt = mid;
            else lt = mid + 1;
        }
        return lt;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        int m = n * n;
        int[] A = new int[n];
        int[] B = new int[n];
        int[] C = new int[n];
        int[] D = new int[n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            A[i] = Integer.parseInt(st.nextToken());
            B[i] = Integer.parseInt(st.nextToken());
            C[i] = Integer.parseInt(st.nextToken());
            D[i] = Integer.parseInt(st.nextToken());
        }

        int[] one = new int[m];
        int[] two = new int[m];
        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                one[idx] = A[i] + B[j];
                two[idx++] = C[i] + D[j];
            }
        }

        Arrays.sort(one);
        Arrays.sort(two);

        m = one.length;
        long answer = 0;
        for (int i = 0; i < m; i++) {
            answer += (upperBound(one, -two[i]) - lowerBound(one, -two[i]));
        }

        System.out.println(answer);
        br.close();
    }
}

 

upperbound와 lowerbound를 활용한 문제

 

처음에는 A[a] + B[b] = -(C[c]+D[d]) 로 if(Arrays.binarySearch(one, -two[i]) >=0 )일때 정답 카운트 하도록 작성했는데,

 

반례 : 

2

0 0 0 0

0 0 0 0

 

정답 16

인데, A[a] + B[b] = -(C[c]+D[d]) 일때, 원소에 중복이 있는 경우에 제대로 카운트 되지 않아 출력이 4가 나왔다.