[백준, BOJ 7453] 합이 0인 네 정수 (java)

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

7453번: 합이 0인 네 정수

---

문제

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 $2^{28}$이다.

출력

합이 0이 되는 쌍의 개수를 출력한다.

728x90

 

예제 입력 1

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

예제 출력 1

5

---

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

public class Main {

	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		int n = Integer.parseInt(br.readLine());
		int[][] arr = new int[4][n];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 4; j++) {
				arr[j][i] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[] ab = new int[n * n]; // a, b 합친 값을 넣을 배열
		int[] cd = new int[n * n]; // c, d 합친 값을 넣을 배열
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				ab[n * i + j] = arr[0][i] + arr[1][j];
				cd[n * i + j] = arr[2][i] + arr[3][j];
			}
		}
		
		// 두 배열 정렬
		Arrays.sort(ab);
		Arrays.sort(cd);
		
		// 투 포인터로 ab, cd 합이 0인 것을 찾는다
		int start = 0; // ab의 앞부분부터 가리킬 포인터
		int end = cd.length - 1; // cd의 뒷부분부터 가리킬 포인터
		long result = 0;
		while(start < ab.length && end >= 0) { // 두 포인터가 범위를 넘기 전까지
			if(ab[start] + cd[end] > 0) { // 0보다 크면
				end--; // cd의 값을 줄여준다
			}
			else if(ab[start] + cd[end] < 0) { // 0보다 작으면
				start++; // ab의 값을 늘려준다
			}
			else { // ab, cd 합이 0이라면
				long abCount = 1; // ab[start]와 같은 수의 개수를 구한다
				long cdCount = 1; // cd[end]와 같은 수의 개수를 구한다
				while(start < ab.length - 1 && ab[start] == ab[start + 1]) {
					abCount++;
					start++;
				}
				while(end > 0 && cd[end] == cd[end - 1]) {
					cdCount++;
					end--;
				}
				result += abCount * cdCount;
				start++;
				end--;
			}
		}
		
		System.out.println(result);
	}

}