[백준 7453] 합이 0인 네 정수 -JAVA // le_effort//

문제만 오랫동안 쳐다본 거 같다. 문제를 이해하지 못했다

저기서 A B C D 배열이 어디있지? 이 생각부터 들었는데

배열이 세로로 되어있는 것이다

즉

A배열      B배열

-45           22

-41           -27

-36            53

-36            30

26            -38

-32           -54

 

그리고 n이 4000이니

A B C D 전부  4중반복문으로 검사를 하면 시간 내에 들어오지 못한다

그래서 두개의 배열을 한 개로 묶어서 해주는데

AB배열 ( 크기가 2일때 A [0]+B [0] A [0]+B [1] A [1]+B [0] A [1]+B [1])

CD 배열 이하 동문

 

그리고 주의할 점이 있는데

밑 코드 중 AB_cnt와 CD_cnt 그리고 ans는 int형을 벗어날 수 있으므로 long으로 써야 한다.

 

그러곤 여타 다른 문제와 같이 투 포인터 알고리즘을 진행하면 된다

import java.io.*;
import java.util.*;
public class Main {
    static int n;
    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];
        
        for(int i=0; i<n; i++) {
            int tmp=0;
            String[] t = br.readLine().split(" ");
            for(int j=0; j<4; j++) {
                arr[j][i] = Integer.parseInt(t[tmp]);
                tmp++;
            }
        }
        
        AB = new int[n*n];
        CD = new int[n*n];
        int idx_ab =0;
        int idx_cd =0;
        for(int i=0; i<n; i++) {
            for(int j=0; j<n; j++) {
                AB[idx_ab] = arr[0][i]+arr[1][j];
                CD[idx_cd] = arr[2][i]+arr[3][j];
                idx_ab++;
                idx_cd++;
            }
        }
        
        Arrays.sort(AB);
        Arrays.sort(CD);
        
        int AB_idx = 0;
        int CD_idx = CD.length-1;
        long ans =0;
        while(AB_idx<AB.length && CD_idx>=0) {
            int AB_sum = AB[AB_idx];
            int CD_sum = CD[CD_idx];
            long AB_cnt =0;
            long CD_cnt=0;
            int total = AB_sum+CD_sum;
            if(total == 0) {
                while(AB_idx<AB.length && AB_sum == AB[AB_idx]) {
                    AB_idx++;
                    AB_cnt++;
                }
                while(CD_idx>=0 && CD_sum == CD[CD_idx]) {
                    CD_idx--;
                    CD_cnt++;
                }
                ans+=AB_cnt*CD_cnt;
            }
            else if(total >0) {
                CD_idx--;
            }
            else {
                AB_idx++;
            }
        }
        System.out.println(ans);
    }
}