문제

7453 합이 0인 네 정수

접근

같은 크기의 4개의 배열 중에서 숫자 한 개씩을 뽑아 합이 0이 되는 경우를 세면 되는 문제입니다. 문제의 특이점이라면 시간제한이 12초, 메모리 제한이 1024MB로 굉장히 널널한 제한 조건을 가집니다.

배열이 주어지고 배열에서 숫자를 뽑아 대소관계를 비교하는 문제는 투 포인터, 이분 탐색으로 풀 수 있습니다. 하지만 위 문제는 배열이 4개입니다. 그렇다면 4개의 배열을 완전 탐색하는 방법으로 해야하는가 싶었지만 배열의 크기 n이 4000으로 시간복잡도가 4000 x 4000 x 4000 x 4000 이 되고 맙니다.

다른 방법을 생각해보면, 투 포인터, 이분 탐색에서 사용한 것처럼 배열을 2개로 줄이는 방법이 있을 수 있습니다. A,B 와 C,D를 묶고 합친 배열 2개를 각각 만들고 2개를 투 포인터, 이분 탐색을 적용할 수 있습니다.

각 배열은 4000 x 4000개의 원소를 가지게 됩니다. 배열을 조합하는데 드는 시간복잡도 역시 4000 x 4000이 됩니다. 하지만 위 문제는 시간복잡도와 공간복잡도가 널널하기 때문에 이는 충분해 보입니다.

그렇다면 1600만개의 배열 두 개를 비교하여 경우를 셀 때의 시간복잡도는 어떻게 될까요? 투 포인터를 기준으로 해도 1600만 * 2이기 때문에 12초 내에 충분히 수행할 수 있어 보입니다.

정리해보겠습니다.
1. 두 배열씩 묶어 새로운 배열 2개 조합
2. 두 개의 새 배열을 투포인터를 통해 합이 0이 되는 경우의 수 세기

풀이

1번의 경우 배열끼리 4000 x 4000 조합하면 되기 때문에 간단합니다.
2번의 경우에는 기존의 투 포인터처럼 배열을 비교하면서 경우의 수를 세면 되겠습니다.

단, 자료형에 대해서 생각해봅시다. 배열에 들어가는 정수의 절댓값은 2의 28승으로 약 3억이 되지 않습니다. 따라서, 4개의 수를 합하더라도 절댓값은 int형의 범위인 -21억 ~ 21억 사이에 존재합니다.

하지만 0이 되는 쌍의 개수는 최대 몇 개가 있을 수 있을까요? 모든 배열의 원소가 4000개 모두 0이라면 4000의 4승이 됩니다. 따라서, 정답이 되는 경우의 수는 long형으로 출력해야 할 것입니다.

코드

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

public class Main {
    static int[] A = new int[4001];
    static int[] B = new int[4001];
    static int[] C = new int[4001];
    static int[] D = new int[4001];
    static int[] arr1;
    static int[] arr2;
    static int n;
    static StringTokenizer st = null;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());
        arr1 = new int[n * n];
        arr2 = 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());
        }

        int idx = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                arr1[idx] = A[i] + B[j];
                arr2[idx] = C[i] + D[j];
                idx++;
            }
        }

        // 정렬
        Arrays.sort(arr1);
        Arrays.sort(arr2);

        System.out.println(searchZero());
    }

    private static long searchZero() {
        long ret = 0;
        int p1 = 0;
        int p2 = n * n - 1;

        while (p1 < n * n && p2 >= 0) {
            int sum = arr1[p1] + arr2[p2];

            if (sum == 0) {
                long cnt1 = 1;
                long cnt2 = 1;

                while (p1 < n * n - 1 && arr1[p1] == arr1[p1 + 1]) {
                    cnt1++;
                    p1++;
                }

                while (p2 > 0 && arr2[p2] == arr2[p2 - 1]) {
                    cnt2++;
                    p2--;
                }

                ret += (cnt1 * cnt2);
                p1++;
                p2--;

            } else if (sum < 0) {
                p1++;
            } else {
                p2--;
            }
        }

        return ret;
    }
}

결과