[백준 / 골드2] 7453번 합이 0인 네 정수 (Java)

lower bound: k값 이상이 처음 나오는 인덱스 구하기
upper bound: k값 초과가 처음 나오는 인덱스 구하기

문제 보기

사용한 것

• 시간 복잡도를 통과하기 위한 이분 탐색
• 이분 탐색 중 lower bound, upper bound 사용

풀이 방법

• a, b, c, d 4가지 배열 존재
• a, b 배열의 임의의 인덱스를 합쳐서 나올 수 있는 결과를 arr1에 저장, 마찬가지로 c, d를 arr2에 저장 -> 2 X N^2
• 이진 탐색 사용하기 위해 arr2를 오름차순 정렬 -> (N^2)log (N^2)
• N^2 만큼 for문 돌면서 lower bound 구하고, upper bound 구하기 -> (N^2) X 2 X log (N^2)
• 따라서 시간 복잡도 -> O((N^2)log (N^2))

코드

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[][] arrs = new long[4][N];
        for (int i = 0; i < N; i++) {
            long[] arr = Arrays.stream(br.readLine().split(" "))
                .mapToLong(Long::parseLong)
                .toArray();
            for (int j = 0; j < 4; j++) {
                arrs[j][i] = arr[j];
            }
        }

        int N2 = N * N;
        long[] arr1 = new long[N2];
        long[] arr2 = new long[N2];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                arr1[N * i + j] = arrs[0][i] + arrs[1][j];
                arr2[N * i + j] = arrs[2][i] + arrs[3][j];
            }
        }

        Arrays.sort(arr2);
        long answer = 0;
        for (int i = 0; i < N2; i++) {
            answer += binarySearch(arr1[i], arr2, N2);
        }

        System.out.println(answer);
    }

    public static int binarySearch(long num, long[] arr, int N) {
        int l1 = 0;
        int r1 = N - 1;
        int m1;
        while (l1 < r1) {
            m1 = (l1 + r1) / 2;
            long added = num + arr[m1];
            if (added >= 0) {
                r1 = m1;
            } else {
                l1 = m1 + 1;
            }
        }
        if (num + arr[r1] != 0) {
            return 0;
        }

        int l2 = 0;
        int r2 = N - 1;
        int m2;
        while (l2 < r2) {
            m2 = (l2 + r2) / 2;
            long added = num + arr[m2];
            if (added > 0) {
                r2 = m2;
            } else {
                l2 = m2 + 1;
            }
        }
        if (num + arr[r2] == 0) {
            r2++;
        }

        return r2 - r1;
    }
}