[SDS 알고리즘 특강 복습] 7453 합이 0인 네 정수 (투포인터)

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

 

 

투포인터로 풀어야 시간복잡도가 가장 줄어드는 문제

^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, A[], B[], C[], D[];
    static int first[], second[];

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

        N = Integer.parseInt(br.readLine());
        A = new int[N];
        B = new int[N];
        C = new int[N];
        D = new int[N];
        first = new int[N*N];
        second = new int[N*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());
        }

        for(int i=0; i<N; i++) {
            for(int j=0; j<N; j++) {
                first[N*i + j] = A[i] + B[j];
                second[N*i + j] = C[i] + D[j];
            }
        }

        Arrays.sort(first);
        Arrays.sort(second);

        int left = 0, right = N*N-1;
        long cnt1, cnt2, ans = 0;
        while(left < N*N && right >= 0) {
            int num1 = first[left];
            int num2 = second[right];

            if(num1 + num2 > 0) {
                right--;
                continue;
            }
            if(num1 + num2 < 0) {
                left++;
                continue;
            }

            cnt1 = cnt2 = 0;
            while (left < N*N) {
                if (first[left] == num1) {
                    cnt1++;
                    left++;
                } else {
                    break;
                }
            }
            while (right >= 0) {
                if (second[right] == num2) {
                    cnt2++;
                    right--;
                } else {
                    break;
                }
            }
            ans += cnt1*cnt2;
        }
        System.out.println(ans);

    }
}