[BaekJoon] 7453 합이 0인 네 정수 (Java)

1.  문제 링크

https://www.acmicpc.net/problem/7453

2.  문제

요약

• 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있습니다.
• A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 4,000보다 작거나 같은 배열의 크기 n이 주어지고 두 번째 줄부터 n개의 줄에 A, B, C, D에 포함되는 정수가 주어집니다.
  • 배열에 들어있는 정수의 절댓값은 최대 $2^28$입니다.
• 출력: 첫 번째 줄에 합이 0이 되는 쌍의 개수를 출력합니다.

3.  소스코드

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

public class Main {
    static int n;
    static int[] A, B, C, D;

    static void input() {
        Reader scanner = new Reader();
        n = scanner.nextInt();
        A = new int[n];
        B = new int[n];
        C = new int[n];
        D = new int[n];

        for(int idx = 0; idx < n; idx++) {
            A[idx] = scanner.nextInt();
            B[idx] = scanner.nextInt();
            C[idx] = scanner.nextInt();
            D[idx] = scanner.nextInt();
        }
    }

    static void solution() {
        int[] AB = new int[n * n], CD = new int[n * n];

        getSequenceSum(A, B, C, D, AB, CD);

        Arrays.sort(AB);
        Arrays.sort(CD);

        long answer = 0L;

        for(int idx = 0; idx < AB.length; idx++) {
            int target = AB[idx];
            answer += binarySearch(target * (-1), CD);
        }

        System.out.println(answer);
    }

    static int binarySearch(int target, int[] sum) {
        int right = upperBound(target, sum);
        int left = lowerBound(target, sum);

        return right - left;
    }

    static int upperBound(int target, int[] sum) {
        int left = 0, right = sum.length;
        while(left < right) {
            int mid = (left + right) / 2;

            if(sum[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }

    static int lowerBound(int target, int[] sum) {
        int left = 0, right = sum.length;
        while(left < right) {
            int mid = (left + right) / 2;

            if(sum[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return right;
    }

    static void getSequenceSum(int[] s1, int[] s2, int[] s3, int[] s4, int[] sum1, int[] sum2) {
        int index = 0;
        for(int idx = 0; idx < n; idx++) {
            for(int idx2 = 0; idx2 < n; idx2++) {
                sum1[index] = s1[idx] + s2[idx2];
                sum2[index] = s3[idx] + s4[idx2];
                index++;
            }
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• A, B 두 배열에서 만들 수 있는 모든 쌍에 대해 더한 값을 구해 AB 배열에 담고 C, D 두 배열에서 만들 수 있는 모든 쌍에 대해 더한 값을 구해 CD 배열에 담습니다.
• AB 배열과 CD 배열을 오름차순으로 정렬합니다.
• AB 배열의 첫 번째 값부터 마지막 값까지 확인하면서 CD 배열에 현재 AB 배열의 값과 더한 값이 0이 되는 값이 존재하는지 이분탐색을 통해 확인하고 개수를 구합니다.
  • Lower Bound 알고리즘을 이용하여 CD 배열에서 (현재 AB 배열의 값 * (-1))과 같은 수의 가장 왼쪽 인덱스를 찾습니다.
  • Upper Bound 알고리즘을 이용하여 CD 배열에서 (현재 AB 배열의 값 * (-1))과 같은 수의 가장 오른쪽 다음 인덱스를 찾습니다.
  • 이렇게 찾은 두 인덱스를 뺌으로서 CD에서의 몇 개의 수가 (현재 AB 배열의 값 * (-1))과 같은지 구합니다.
  • 이 과정을 모든 AB 배열의 수에 대해서 진행하고 개수를 누적합니다.