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

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

public class FourIntegersWithSumOfZero {
    static BufferedReader br;
    static StringTokenizer st;
    static int n;
    static long ans;
    static int[] a, b, c, d;
    static long[] left, right;

    public static void main(String[] args) throws IOException{
        input();
        calculate();
        Arrays.sort(left);
        Arrays.sort(right);
        getSum();
        System.out.println(ans);
    }

    static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        a = new int[n];
        b = new int[n];
        c = new int[n];
        d = new int[n];
        for(int i = 0; i < n; i++) {
            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());
        }
        left = new long[n*n];
        right = new long[n*n];
    }

    static void calculate() {
        int cnt = 0;
       for(int i = 0; i < n; i++) {
           for(int j = 0; j < n; j++) {
               left[cnt] = a[i] + b[j];
               right[cnt] = c[i] + d[j];
               cnt++;
           }
       }
    }

    static void getSum() {
        int start = 0;
        int end = right.length - 1;

        while(start < left.length && end >= 0) {
            long leftVal = left[start];
            long rightVal = right[end];
            long sum = leftVal + rightVal;
            if(sum == 0) {
                long leftCnt = 0;
                while(start < left.length && left[start] == leftVal) {
                    leftCnt++;
                    start++;
                }
                long rightCnt = 0;
                while(end >= 0 && right[end] == rightVal) {
                    rightCnt++;
                    end--;
                }
                ans += leftCnt * rightCnt;
            }
            if(sum < 0) start++;
            if(sum > 0) end--;
        }
    }
}

투포인터 알고리즘을 사용한 문제였다. 연산량이 많이질 수 있는문제이기 때문에 단순히 O(N^4)로 풀게되면 시간초과가 난다.

 

문제의 핵심은 a, b, c, d 네 개의 배열을 각각 두개씩 먼저 더하는 것이다.

 

a배열과 b배열의 모든 쌍의 합을 리스트에 저장하고 c배열과 d배열의 모든 쌍 역시 다른 리스트에 저장한다.

 

그리고 그 리스트를 각각 left, right라고 하고 정렬을 한 후에 두 배열에 대해서 투포인터로 합을 찾는다. 값을 계속 찾다가 합이 0인 값들을 찾으면 리스트안에 동일한 값이 있는지 탐색 후에 카운트를 알맞게 올려준다.

 

처음엔 ArrayList로 값들을 받아서 Collecntions.sort()를 사용했는데 시간초과가 났다. 그래서 배열로 자료구조를 바꾸고 Arrays.sort()로 했더니 AC를 받을 수 있었다. 다른 분이 올리신걸 보니 Collections는 merge sort를 사용하고 Arrays는 dual pivot quick sort를 사용해서 그렇다더라. 나중에 듀얼 피봇 퀵소트가 어떤식으로 작동하는지 알아봐야 겠다.