bj7453(합이 0인 네 정수) - 구현, 정렬, 투포인터, 중간에서 만나기

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

 

완전 탐색으로 하면 4000*4000*4000*4000 이기에 12초라도 시간초과가 나는 문제이다.

중간에서 만나기라는 알고리즘은

1개의 배열을 2개로 나눠서 투 포인터로 더 빠른 루프를 돌릴 수 있는 방법이다.

 

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

public class Main {
    static int n;
    static int[] A,B,C,D;
    static long[] AB, CD;
    static StringTokenizer stringTokenizer;
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException {
        initialize();
        System.out.println(solve());
    }

    private static long solve() {
        makeAB_CD();

        long cnt = 0;
        int AB_i = 0;
        int CD_i = n * n - 1;

        while(AB_i < n * n && CD_i >= 0){
            if(AB[AB_i] + CD[CD_i] > 0){
                CD_i = handleCD_i(CD_i);
                continue;
            }
            if(AB[AB_i] + CD[CD_i] < 0){
                AB_i = handleAB_i(AB_i);
                continue;
            }
            if(AB[AB_i] + CD[CD_i] == 0){
                int nextCD_i = handleCD_i(CD_i);
                int nextAB_i = handleAB_i(AB_i);
                if(nextAB_i - AB_i != 1 || CD_i - nextCD_i != 1){
                    long plusCnt = (long) (nextAB_i - AB_i) * (CD_i - nextCD_i);
                    cnt += plusCnt;
                }else{
                    cnt++;
                }
                AB_i = nextAB_i;
                CD_i = nextCD_i;
            }
        }
        return cnt;
    }

    private static int handleAB_i(int abI) {
        long prevValue = AB[abI++];
        while(abI < n*n && AB[abI] == prevValue){
            prevValue = AB[abI++];
        }
        return abI;
    }

    private static int handleCD_i(int cdI) {
        long prevValue = CD[cdI--];
        while(cdI >= 0 && CD[cdI] == prevValue){
            prevValue = CD[cdI--];
        }
        return cdI;
    }

    private static void makeAB_CD() {
        AB = new long[n * n];    //16000000
        CD = new long[n * n];    //16000000      //16000000번으로 투포인터
        //1200000000

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

    private static void initialize() throws IOException {
        n = Integer.parseInt(bufferedReader.readLine());
        A = new int[n];
        B = new int[n];
        C = new int[n];
        D = new int[n];
        for(int i = 0; i < n; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            A[i] = Integer.parseInt(stringTokenizer.nextToken());
            B[i] = Integer.parseInt(stringTokenizer.nextToken());
            C[i] = Integer.parseInt(stringTokenizer.nextToken());
            D[i] = Integer.parseInt(stringTokenizer.nextToken());
        }
    }
}