[BOJ] 7453 - 합이 0인 네 정수 JAVA

www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

문제

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

5

 

 

 

 

 

 

 

풀이 .

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

public class Main {
    static BufferedReader br = null;
    static StringTokenizer st = null;
    static int[] A, B, C, D, AB, CD;
    static int N;

    public static int upperBound(int[] arr, int target) {
        int min = 0;
        int max = arr.length;
        while(min < max) {
            int mid = (min + max) / 2;
            if(arr[mid] <= target) {
                min = mid + 1;
            }else {
                max = mid;
            }
        }
        return max;
    }

    public static int lowerBound(int[] arr, int target) {
        int min = 0;
        int max = arr.length;
        while(min < max) {
            int mid = (min + max) / 2;
            if(CD[mid] >= target) {
                max = mid;
            }else {
                min = mid + 1;
            }
        }
        return max;
    }

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

        A = new int[N];
        B = new int[N];
        C = new int[N];
        D = new int[N];

        // 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());
        }

        // N^2
        AB = new int[N * N];
        CD = new int[N * N];
        int idx = 0;
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N;j++) {
                AB[idx] = A[i] + B[j];
                CD[idx] = C[i] + D[j];
                idx += 1;
            }
        }
        Arrays.sort(AB);
        Arrays.sort(CD);

        // N^2 * 2 * logN
        long ans = 0;
        for(int num : AB) {
            ans += upperBound(CD, -num) - lowerBound(CD, -num);
        }
        System.out.println(ans);
    }
}

 

N^4로 완전탐색해서 구할 수 있지만 시간초과가 나버린다.

 

A와B, C와D에 대해서 2N짜리 크기의 배열을 만들고 그 둘로 검사를 실행한다.

A + B + C + D = 0 을 A + B = -(C + D)로 바꿔서 CD배열에서 -AB를 찾는 것이다.

 

AB에 대해서는 이분탐색을 실행하지 않기 때문에 CD만 정렬을 했는데 시간초과가 발생헀다.

다시 AB까지 정렬을 실행하고 돌리니까 정답 처리.

 

일을 더 오래 했는데 통과되는 기이한 현상?

-> 둘 다 정렬을 하고 실행하면 공간 지역성에 의해 오히려 더 빨리 처리된다고 한다.

 

내 수준에서 문제를 풀면서 지역성의 영향까지 받게될 줄은 몰랐다..

 

 

 

위 방법 말고도 HashMap을 이용해서도 처리가 가능할 듯 하다.

AB, CD에 대한 HashMap에 (숫자, 개수)를 담고 탐색만 하는 것.

귀찮아서 짜보지는 않았다.

 

AB, CD에 대한 투포인터로 탐색도 가능할 듯.