[JAVA/투포인터] 백준 7453 합이 0인 네 정수

1. 문제

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

7453번: 합이 0인 네 정수

 

2. 풀이

 

숫자가 A, B, C, D 총 네종류가 있고 합이 0이 되는 A, B, C, D 쌍을 구해야 한다. 이를 A와 B의 가능한 모든 합과 C와 D의 가능한 모든 합으로 나누어 구하고 A와 B의 합과 C와 D의 합 중 0이 되는 쌍을 찾는다. 즉, (A+B) + (C+D) 이런식으로 나누어 생각하는 것이다.

A와 B의 합과 C와 D의 합은 가능한 모든 경우의 수를 구하고, 이들을 각각 오름차순으로 정렬한다. 이 후 투포인터를 사용해 0이 되는 경우를 찾는다. 이때, A와 B의 합, C와 D의 합은 중복되는 숫자가 있을 수 있으므로 while문을 사용해 겹치는 숫자들을 따로 구해 더한다. 

 

3. 코드

 

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

// 투포인터

public class Main_7453_two_point {
    
    static long[][] numbers;
    static long[] AB;
    static long[] CD;
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
        int n = Integer.parseInt(br.readLine());
        numbers = new long[n][4];
        AB = new long[n * n];
        CD = new long[n * n];
        
        for(int i = 0; i < n; i++) {
            String[] ss = br.readLine().split(" ");
            for(int j = 0; j < 4; j++) {
                numbers[i][j] = Integer.parseInt(ss[j]);
            }
        }
        
        // A,B의 합, C, D의 합 배열 만듦
        int idx = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                AB[idx] = numbers[i][0] + numbers[j][1];
                CD[idx] = numbers[i][2] + numbers[j][3];
                idx++;
            }
        }
        
        // 배열 정렬
        Arrays.sort(AB);
        Arrays.sort(CD);
        
        // 투포인터
        long answer = 0, sum = 0;
        int abIdx = 0, cdIdx = n*n - 1;
        while(abIdx < n*n && cdIdx >= 0) {
            sum = AB[abIdx] + CD[cdIdx];
            if(sum == 0) { // 합이 0
                
                // 중복 숫자 구함
                long nowAB = AB[abIdx];
                int abDupCnt = 0;
                while(abIdx < n * n && AB[abIdx] == nowAB) {
                    abIdx++;
                    abDupCnt++;
                }
                
                long nowCD = CD[cdIdx];
                int cdDupCnt = 0;
                while(cdIdx >= 0 && CD[cdIdx] == nowCD) {
                    cdIdx--;
                    cdDupCnt++;
                }
            
                answer += (long)abDupCnt * (long)cdDupCnt;
                
            }else if(sum < 0) {
                abIdx++;
            }else {
                cdIdx--;
            }
        }
        

        
        System.out.println(answer);
    }
}