[백준] 7453번 - 합이 0인 네 정수 (java)

Baekjoon 7453 - 합이 0인 네 정수 (클릭 시 이동)

문제

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

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

 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
12 초 (추가 시간 없음)	1024 MB	23934	5805	3305	22.478%

 

입력

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

 

출력

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

 

풀이

숫자가 커서 그렇지 시간 제한과 메모리 제한이 꽤 넉넉하다.

N이 4000이라고 가정해보면 A와 B를 합쳐서 만들 수 있는 숫자 합의 갯수는 4000 x 4000개인 1600만개이다.

각 숫자는 2^28이 최대이므로 두 숫자를 더해봐야 2^29이므로 int형으로 충분하다.

그렇다면 4개의 배열이 있으니 3200만개의 int형 배열이 필요한데 int는 4byte이므로 32,000,000 x 4Byte = 128,000,000Byte = 125,000 KB = 약 122.1MB이므로 충분하다.(이러한 배열을 만드는데의 시간복잡도는 N^2)

그렇다면 16만개짜리 배열 두개를 정렬하는 것도 NlogN을 두번 수행하게 되므로 역시 충분하다.

 

이 두개의 배열을 이분탐색으로 0이 되는 수를 찾으면 된다.

주의해야할 점은 두 숫자의 합이 같을 수 있다는 것이다.

수가 같으면 그 숫자의 갯수를 세서 곱해주는 과정이 필요하다.

if (sum == 0) {
    while (first <= end - 2 && preSum[0][first] == preSum[0][first + 1]) {
        firstCnt++; //해당 숫자의 갯수
        first++;    //배열의 인덱스
    }
    while (0 < second && preSum[1][second] == preSum[1][second - 1]) {
        secondCnt++;    
        second--;
    }
    answer += (long) firstCnt * secondCnt;
}

또한 합의 최댓값은 2^28 x 4 = 2^30 이므로 int형으로 충분하지만

합의 갯수는 모든 수가 0일 경우 배열에서 만들 수 있는 모든 숫자가 0일 수 있다. 16,000,000 x 16,000,000 = 256조 ( long )

최종 소스코드

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

public class BJ_G2_7453_합이_0인_네_정수 {

    static int N;
    static long answer = 0;
    static int[][] data;
    static int preSum[][];
    static StringTokenizer st;

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

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

        preSum = new int[2][N * N];
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                preSum[0][count] = data[i][0] + data[j][1];
                preSum[1][count++] = data[i][2] + data[j][3];
            }
        }
        Arrays.sort(preSum[0]);
        Arrays.sort(preSum[1]);
        int first = 0;
        int second = preSum[0].length - 1;

        int end = N * N;
        while (first < end && 0 <= second) {
            int sum =  preSum[0][first] + preSum[1][second];
            int firstCnt =1;
            int secondCnt = 1;
            if (sum == 0) {
                while (first <= end - 2 && preSum[0][first] == preSum[0][first + 1]) {
                    firstCnt++;
                    first++;
                }
                while (0 < second && preSum[1][second] == preSum[1][second - 1]) {
                    secondCnt++;
                    second--;
                }
                answer += (long) firstCnt * secondCnt;
            }

            if (sum < 0) {
                first++;
            } else{
                second--;
            }
        }
        System.out.println(answer);
    }
}