[백준] 7453번 자바 합이 0인 네 정수

문제 출처 

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

7453번: 합이 0인 네 정수

 

 

접근 방식 및 풀이

- 1208번과 비슷한 문제

[Algorithm/백준] - [백준] 1208번 자바 부분수열의 합2

 

- 4개의 배열을 2개의 배열의 부분합으로 만든 후, 2개의 배열을 투포인트 알고리즘을 적용한다.

 

 

소스 코드 

import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    static long[][] arr;
    static long[] arrab, arrcd;
    static long count=0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
 
        arr = new long[n][4];
 
        arrab = new long[n*n];
        arrcd = new long[n*n];
 
        for (int i = 0; i <n ; i++) {
            arr[i][0] = sc.nextLong();
            arr[i][1] = sc.nextLong();
            arr[i][2] = sc.nextLong();
            arr[i][3] = sc.nextLong();
        }
 
        // 두배열의 부분합 구하기
        int k =0;
        for (int i = 0; i <n ; i++) {
            for (int j = 0; j <n ; j++) {
                arrab[k] = arr[i][0] + arr[j][1];
                arrcd[k] = arr[i][2] + arr[j][3];
                k++;
            }
        }
 
        Arrays.sort(arrab);
        Arrays.sort(arrcd);
 
        int leftIdx = 0;
        int rightIdx = (n*n) -1;
        while (leftIdx < (n*n) && rightIdx>=0){// 전체 범위 제한둠
 
            long lv = arrab[ leftIdx];
            long rv = arrcd[rightIdx];
 
            if(lv+rv ==0){
                long lc = 0;
                while(leftIdx < arrab.length && arrab[leftIdx] == lv){
                    lc++;
                    leftIdx++;
                }
                long rc = 0;
                while(rightIdx >= 0 && arrcd[rightIdx] == rv){
                    rc++;
                    rightIdx--;
                }
                count += (rc*lc);
            }
            if(lv+rv>0){
                rightIdx--;
            }
            if(lv+rv<0){
                leftIdx++;
            }
        }
        // 4개의 배열을 모두 사용하여 만들었기 때문에 공집합인 경우는 없다.
        System.out.println(count);
    }
}
    

 

 

결과