boj 7453: 합이 0인 네 정수

2020/07/13 - [알고리즘 공부] - boj 1208: 부분집합의 합2

boj 1208: 부분집합의 합2

위 글과 마찬가지 방법으로 풀면 된다.

 

크기 N이 주어졌을 때, 배열 A, B, C, D가 주어지면

A[a]+B[b]+C[c]+D[d]==0인 a, b, c, d의 쌍을 구하는 문제이다.

 

4중 for문을 돌리면 O(N^4)만에 풀 수 있지만,

A[a]+B[b]와 C[c]+D[d]를 순차적으로 구한 뒤 합이 0인지 찾는다면 O(N^2)만에 풀 수 있다.

 

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();

		long A[] = new long[n];
		long B[] = new long[n];
		long C[] = new long[n];
		long D[] = new long[n];
		for (int i = 0; i < n; i++) {
			A[i] = in.nextLong();
			B[i] = in.nextLong();
			C[i] = in.nextLong();
			D[i] = in.nextLong();
		}

		long left[] = new long[n * n];
		long right[] = new long[n * n];
		int index = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				left[index] = A[i] + B[j];
				right[index] = C[i] + D[j];
				index++;
			}
		}

		Arrays.sort(left);
		Arrays.sort(right);

		long ans = 0;
		int leftIndex = 0;
		int rightIndex = n * n - 1;
		while (leftIndex < n * n && rightIndex >= 0) {
			long leftSum = left[leftIndex];
			long rightSum = right[rightIndex];
			if (leftSum + rightSum == 0) {
				long leftSame = 0;
				long rightSame = 0;
				while (leftIndex < n * n && leftSum == left[leftIndex]) {
					leftIndex++;
					leftSame++;
				}
				while (rightIndex >= 0 && rightSum == right[rightIndex]) {
					rightIndex--;
					rightSame++;
				}
				ans += leftSame * rightSame;
			} else if (leftSum + rightSum > 0) {
				rightIndex--;
			} else {
				leftIndex++;
			}
		}
		System.out.println(ans);
	}
}