BOJ 7453)4 Values whose Sum is 0

Wonjun Lee·2025년 11월 23일

문제 링크

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

입력

The first line of the input contains the size of the lists n (this value can be as large as 4000). We then have n lines containing four integer values (with absolute value as large as $2^{28}$ ) that belong respectively to A, B, C and D .

출력

For each input, your program has to write the number quadruplets whose sum is zero.

풀이과정

문제 이해

n개의 정수로 이루어진 4개 숫자 리스트에서 각각 하나씩 정수를 선택했을 때, 그 합이 0이 되는 경우의 수를 구하는 문제.

주어지는 입력이 리스트이기 때문에 중복되는 숫자가 생길 수 있다.

접근

1. 무식한 방법

A,B,C,D 네 리스트의 각 정수들을 하나씩 대응시켜가면서 그 합을 검사할 수 있다.

이럴 경우 O(N^2)의 시간복잡도를 갖게되며, n이 4000일 때, $(2^2 \times 10^4)^4 = 2^8 \times 10^{16}$ 번의 연산이 수행된다.

2. 미리 합을 구성하는 방법.

A,B의 합과 C,D의 합을 미리 구한 뒤 리스트에 저장하고 두 정수의 합이 0이 되는 수를 세는 것은 조금 더 빨리 수행될 수 있다.

최대 16000000개의 정수가 한 리스트에 들어가게 되고, 한 리스트를 정렬하고 탐색은 해시 또는 이진탐색을 활용하여 해결하면 $2 \times (2^4 \times 10^7) log_{2}(2^4 \times 10^7)$ (1번은 정렬, 1번은 A,B 리스트 합을 구한 리스트 정수에 대해 정렬된 C, D의 합을 구한 리스트에서 이진탐색 비용)
으로 제한 시간인 12초 내에 수행될 수 있다.

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

public class Main {
    public static int A = 0, B = 1, C = 2, D = 3;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[][] valueSet = new long[4][n];
        long[] abSum = new long[n * n];
        long[] cdSum = new long[n * n];

        for (int i = 0; i < n; i++) {
            String[] tokens = br.readLine().split(" ");
            valueSet[A][i] = Long.parseLong(tokens[0]);
            valueSet[B][i] = Long.parseLong(tokens[1]);
            valueSet[C][i] = Long.parseLong(tokens[2]);
            valueSet[D][i] = Long.parseLong(tokens[3]);
        }

        HashMap<Long, Long> cntMap = new HashMap<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                abSum[i * n + j] = valueSet[0][i] + valueSet[1][j];
                cdSum[i * n + j] = valueSet[2][i] + valueSet[3][j];
            }
        }

        long cnt = 0;
        Arrays.sort(cdSum);
        for (int i = 0; i < abSum.length; i++) {
            int idx = Arrays.binarySearch(cdSum, -abSum[i]);
            // 여러개 있을 수도 있음.
            cnt += (idx >= 0 ? getCount(cdSum, idx, cntMap) : 0);
        }
        System.out.println(cnt);
    }

    public static long getCount(long[] ary, int pos, HashMap<Long, Long> cache) {
        // 캐시를 사용해서 미리 구해두면 빠름.
        if(cache.containsKey(ary[pos])) return cache.get(ary[pos]);
        int left = pos - 1; int right = pos; long cnt = 0;
        while(left >= 0 && ary[left] == ary[pos]) {
            cnt++; left--;
        }
        while(right < ary.length && ary[right] == ary[pos]) {
            cnt++; right++;
        }
        cache.put(ary[pos], cnt);
        return cnt;
    }
}

다른 방법

다른 사람 코드를 분석해보고 더 나은 해법을 파악해보았다.

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        long[] a = new long[n];
        long[] b = new long[n];
        long[] c = new long[n];
        long[] d = new long[n];

        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            a[i] = Long.parseLong(st.nextToken());
            b[i] = Long.parseLong(st.nextToken());
            c[i] = Long.parseLong(st.nextToken());
            d[i] = Long.parseLong(st.nextToken());
        }

        long[] ab = new long[n * n];
        int idx = 0;
        for(long i: a) {
            for(long j: b) {
                ab[idx++] = i + j;
            }
        }

        long[] cd = new long[n * n];
        idx = 0;
        for(long i: c) {
            for(long j: d) {
                cd[idx++] = i + j;
            }
        }

        Arrays.sort(ab);
        Arrays.sort(cd);

        int left = 0;
        int right = n * n - 1;

        long ans = 0;
        while(left < n * n && right >= 0) {
            long sum = ab[left] + cd[right];

            if(sum == 0) {
                long abV = ab[left];
                long cdV = cd[right];

                long abC = 0;
                long cdC = 0;

                while(left < n * n && ab[left] == abV) {
                    left++;
                    abC++;
                }
                while(right >= 0 && cd[right] == cdV) {
                    right--;
                    cdC++;
                }

                ans += abC * cdC;
            }else if(sum > 0) {
                right--;
            }else {
                left++;
            }
        }
        System.out.print(ans);
    }
}