7453 - 합이 0인 네 정수 (Java)

---

📌 문제 요약

네 개의 정수 배열 A, B, C, D가 있을 때
A[a] + B[b] + C[c] + D[d] == 0 을 만족하는 (a, b, c, d) 쌍의 개수를 구하는 문제

• 배열 길이 N ≤ 4000
• 각 배열의 값은 정수 (절댓값 ≤ 2²⁸)

---

🔍 시도 요약 및 시행착오

✅ 1. 해시맵 사용

• A + B의 합을 모두 해시맵에 저장
• C + D의 합의 -1배가 map에 존재하는지 탐색

❌ 실패 사유:
해시맵 조회는 평균 O(1)이지만, 객체 박싱/GC/해시 충돌 등으로 시간초과 발생

---

✅ 2. 이분 탐색으로 존재 여부 확인

• A + B, C + D 합을 각각 배열로 만들고
• C + D 배열을 정렬한 뒤, -ab[i] 값이 존재하는지 binarySearch로 체크

❌ 실패 사유:
이분 탐색으로 값이 존재하는지는 확인 가능하지만,
몇 번 등장하는지를 정확히 세지 않아서 오답 발생

---

✅ 3. 이분 탐색 + 중복값 개수 파악 시도

• -ab[i] 값을 기준으로 ±0.5를 기준으로 binarySearch 범위 계산

❌ 실패 사유:
부동소수점 연산 오차로 인해 0.0 ≠ -0.0처럼 비교 실패,
게다가 int 범위 초과 → long 사용 필요

---

✅ 4. 예외 처리 및 자료형 보정

• ab[i] == 0.0일 때 -0.0 비교 오류 → 0.0로 강제
• 정답형 long으로 수정

✅ 성공!

---

✅ 최종 1: 이분 탐색 + 중복 개수 카운팅 ✔

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

public class Main {
    static int N;
    static int[][] map;

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

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

        double[] ab = new double[N * N];
        double[] cd = new double[N * N];
        int idx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ab[idx] = map[i][0] + map[j][1];
                cd[idx] = map[i][2] + map[j][3];
                idx++;
            }
        }

        Arrays.sort(cd);

        long result = 0;
        for (int i = 0; i < ab.length; i++) {
            double key = (ab[i] == 0.0) ? 0.0 : -ab[i];

            int lower = -(Arrays.binarySearch(cd, key - 0.5) + 1);
            int upper = -(Arrays.binarySearch(cd, key + 0.5) + 1);
            result += (upper - lower);
        }

        System.out.println(result);
    }
}

---

✅ 최종 2: 투 포인터 방식 (더 빠름) 🚀

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

public class Main {
    static int N;
    static int[][] map;

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

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

        int[] ab = new int[N * N];
        int[] cd = new int[N * N];
        int idx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                ab[idx] = map[i][0] + map[j][1];
                cd[idx] = map[i][2] + map[j][3];
                idx++;
            }
        }

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

        int start = 0;
        int end = cd.length - 1;
        long result = 0;

        while (start < ab.length && end >= 0) {
            int sum = ab[start] + cd[end];

            if (sum == 0) {
                int abVal = ab[start];
                int cdVal = cd[end];
                long abCount = 0, cdCount = 0;

                while (start < ab.length && ab[start] == abVal) abCount++;
                while (end >= 0 && cd[end] == cdVal) cdCount--;

                result += abCount * cdCount;
            } else if (sum < 0) {
                start++;
            } else {
                end--;
            }
        }

        System.out.println(result);
    }
}

---

📊 성능 비교

방법	시간복잡도	장점	단점
이분 탐색 + 개수 카운팅	O(N² log N)	이론적으로 간단	부동소수점 오차, 예외처리 필요
✅ 투 포인터	O(N²)	구현 간단 + 빠름	정렬 필요

---

💡 배운 점 요약

• 정답형은 항상 자료형 검토 (특히 int → long 고려)
• 중복값을 찾을 때는 존재 여부가 아니라 개수가 핵심
• 실수 비교에는 항상 오차를 고려해야 하며, 가능하면 정수형으로 처리
• 정렬된 두 배열의 합 문제는 투 포인터가 정석

---