[BOJ] 7453. 합이 0인 네 정수 - (Java)

[BOJ] 7453. 합이 0인 네 정수 - (Java)

Problem

제출일 : 2020-03-17

문제 풀이 시간 : 1H

난이도 : ★★★★

---

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

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

Input

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 $2^{28}$이다.

Output

합이 0이 되는 쌍의 개수를 출력한다.

Example

input

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

output

5

Solution & Inpression

low_bound와 upper_bound를 활용하는 문제, 아이디어를 도출해 내는 것이 중요함.

시간초과를 벗어나기 위해 BufferedReader를 사용했으며 ArrayList대신 배열을 이용함.

Code

언어 : JAVA

메모리 : 140708 kb

실행 시간 : 2552 ms

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

public class Main {
    static int N;
    static int[][] data;
    static int[] AB, CD;
    static long ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());

        data = new int[4][N];
        for (int j = 0; j < N; j++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < 4; i++) {
                data[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        AB = new int[N * N];
        CD = new int[N * N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                AB[i * N + j] = data[0][i] + data[1][j];
                CD[i * N + j] = data[2][i] + data[3][j];
            }
        }

        Arrays.sort(CD);

        for (int i : AB) {
            int high = upper_bound(CD, -i);
            int low = lower_bound(CD, -i);
            ans += high - low;
        }

        System.out.println(ans);
    }

    // lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치
    private static int lower_bound(int[] arr, int val) {
        int start = 0;
        int end = arr.length;
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (arr[mid] >= val) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    // upper bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치
    private static int upper_bound(int[] arr, int val) {
        int start = 0;
        int end = arr.length;
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (arr[mid] <= val) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}