[백준] 7453번 : 합이 0인 네 정수 - 자바(JAVA)

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

7453번: 합이 0인 네 정수

 

문제 해석

정수로 이루어진 크기가 같은 배열 4개가 존재합니다.

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

 

배열의 크기 최대(4000)

배열에 들어있는 정수의 최대는 2^28입니다.

 

문제 풀이 전 설계

시간 제한이 12초인 점이 가장 먼저 눈에 들어왔습니다.

또한 정수의 절댓값은 2^28인데 4개의 배열이 있으니 최대로 나올 수 있는 수는 2^28 * 4 = (2^28) *( 2^2) = 2^30

 

2^30 = 2^10 * 2^10 * 2^10 입니다.

즉, 1024 * 1024 * 1024 = 대략 10억입니다.

 

가장 쉽게 떠오르는 생각은 4중 for문으로 쌍의 개수를 구하는 방법입니다.

시간복잡도는 O(N^4) = 4000 * 4000 * 4000 * 4000 = 대략 300조 정도로 불가능해 보입니다.

 

합의 최댓값은 int형으로 충분하지만 합의 개수는 모든 수가 0일 경우 배열에서 만들 수 있는 모든 숫자가 0일 수 있습니다.

대략 300조(long 타입 필요)

 

4개의 배열을 1개의 배열로 합친후 정렬하여 투포인터를 사용해야 하나? 라는 생각이 떠오르지만 어떻게 해야할지 감이 오지 않습니다.

 

문제 풀이

 2중 반복문을 돌리면서 2개의 배열으로 재구성합니다.

A와 B의 합을 구한 배열 AB

C와 D의 합을 구한 배열 CD

 

이후에 AB의 합과 CD의 합을 오름차순으로 정렬합니다.

AB는 최솟값부터 CD는 최댓값부터 투 포인터 출발합니다.

AB+CD의 합이 0일 경우 중복인 합 개수까지 고려해서 정답을 더해줍니다.

AB+CD > 0 인 경우 CD를 낮춰줍니다.

AB+CD < 0 인 경우 AB를 높여줍니다.

 

위의 풀이말고도 upper_bound 와 lower_bound를 통해 이진탐색을 통해 답을 찾는 방법도 존재합니다.

 

 

코드

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

public class Main_7453_합이0인네정수 {

    static final int ARRAY_COUNT = 4;

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

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

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

        for (int i = 0; i < n; i++) {
            StringTokenizer 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[] AB = new int[n*n];
        int[] CD = new int[n*n];

        int index = 0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                AB[index] = A[i] + B[j];
                CD[index] = C[i] + D[j];
                index++;
            }
        }

        Arrays.sort(AB);
        Arrays.sort(CD);

        int right = (n*n)-1;
        long answer =0;

        for(int left=0; left<n*n && right>=0;){
            long sum = AB[left] + CD[right];

            if(sum > 0){
                right--;
            } else if(sum < 0){
                left++;
            } else{
                //합이 0인 경우
                int curAB = AB[left];
                int curCD = CD[right];
                long ABCount = 0;
                long CDCount = 0;
                while(left<(n*n) && curAB == AB[left]){
                    left++;
                    ABCount ++;
                }
                while(right >=0 && curCD == CD[right]){
                    right--;
                    CDCount++;
                }
                answer += (ABCount * CDCount);
            }

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