백준 7453[자바] java 합이 0인 네 정수

 

문제 링크:https://www.acmicpc.net/problem/7453

7453번: 합이 0인 네 정수

 

▶문제

 

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

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

 

▶입력

 

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

 

▶출력

 

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

 

▶해설

 

문제를 분해합니다. 4개의 수를 더했을 때 0이 되는 순서쌍 찾기입니다.

 

문제의 입력이 4000이므로 4개의 배열에서 하나씩 선택했을 때 모든 수를 탐색하는데 4000*4000*4000*4000으로 시간초과가 발생합니다. 따라서 이분 탐색 혹은 투 포인터를 이용해서 탐색하는 횟수를 줄여야 합니다. 

 

이분 탐색, 투포인터의 조건은 정렬된 배열이어야 합니다. 이때 4개의 배열에 대해서 이분 탐색과 투 포인터를 적용할 수는 없습니다. 따라서 배열을 압축해야 하는데 4개의 배열을 한 개로 압축하는 것은 위의 말한 탐색 수와 같은 시간 복잡도를 가집니다. 2개의 배열로 압축해서 진행합니다. 

 

배열1: A와B배열들의 합

배열2: C와 D배열들의 합

 

이렇게 했을 때 최대 1600만 배열이 2개 나오게 됩니다. 해당 배열은 A와 B의 모든 순서쌍, C와 D의 모든 순서쌍의 가지고 있습니다. 이제 두 배열을 이용해서 투 포인터를 적용합니다.

 

시작점은 0이고, 끝점은 n*n-1입니다. 그 이유는 n의 길이를 가지는 배열 2개의 모든 순서쌍 덧셈을 진행한다면 크기가 n*n입니다. 

 

이제 AB배열의 시작점은 0, CD배열의 시작점은 n*n-1로 시작해서 탐색을 진행합니다. 

 

while(left<n*n && right>=0){
    long num1 = AB[left];
    long num2 = CD[right];
    long sum = num1+num2;
    if(sum<0){
        left++;
    }
    else if(sum>0) {
        right--;
    }
    else{
        
    }
}

 

중요한점은 AB배열의 요소와 CD배열의 요소가 합쳐졌을 때 0이었을 때 추가적인 연산을 진행해야 합니다. 그 이유는 같은 값을 가진 인덱스가 존재할 수 있기 때문입니다. 따라서 아래와 같이 코드를 추가합니다.

 

AB에서 현재 인덱스의 값과 같은 값의 개수 * CD에서 현재 인덱스의 값과 같은 값의 개수

 

else{
    long temp1=0;
    long temp2=0;
    while(left<n*n && num1==AB[left]){
        left++;
        temp1++;
    }
    while(right>=0 && num2==CD[right]){
        right--;
        temp2++;
    }
    result+=temp1*temp2;
}

 

전체 코드

 

import javax.xml.transform.SourceLocator;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.*;
import java.util.*;

public class Main {

    static int n;
    static long result;
    static int [][]arr;
    static int [] AB;
    static int [] CD;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        arr = new int[4][n];

        AB = new int[n*n];
        CD = new int[n*n];

        for(int j=0; j<n; j++){
            String[] s = br.readLine().split(" ");
            for(int i=0; i<4; i++){
                arr[i][j] = Integer.parseInt(s[i]);
            }
        }

        int k=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                AB[k++]=arr[0][i]+arr[1][j];
            }
        }

        k=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                CD[k++]=arr[2][i]+arr[3][j];
            }
        }


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

        solve();

        System.out.println(result);

    }

    private static void solve(){
        int left=0;
        int right = n*n-1;

        while(left<n*n && right>=0){
            long num1 = AB[left];
            long num2 = CD[right];
            long sum = num1+num2;
            if(sum<0){
                left++;
            }
            else if(sum>0) {
                right--;
            }
            else{
                long temp1=0;
                long temp2=0;
                while(left<n*n && num1==AB[left]){
                    left++;
                    temp1++;
                }
                while(right>=0 && num2==CD[right]){
                    right--;
                    temp2++;
                }
                result+=temp1*temp2;
            }
        }
    }
}