[해싱] 백준 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에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.

출력

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

 

 

브루트 포스로 4중포문을 돌면서 하면 시간초과 발생.

A B C D 4개의 배열을 2개씩 묶는다

그래서 A B의 합을 저장한 AB (N*N 사이즈) C D 합을 저장한 CD를 두고 정렬을 한다

AB인덱스는 0부터 CD 인덱스는 idx부터 투포인터로 반대방향으로 내려오면서 더해서 0 인 구간을 찾는다

만약 더한결과가 0보다 작다면 AB값이 작은 것이니 인덱스를 하나 올리고 크다면 CD값이 큰것이니 인덱스를 하나내린다.

여기서 사용해야하는 스킬은

AB값이 -3 -3 2 2 

CD값이 2 7 3 3 

인 경우 -3 3에 대해 0이 발생할 것인데 이것을 세는 방식은 서로 상대배열의 인덱스는 고정하고 자신의 인덱스를

늘리거나 줄이면서 0이 되는 갯수를 세고 각 갯수의 곱을 내면 -3 3쌍으로 0이되는 모든 경우의 수를 구할 수 있다.

이것을 정답값에 더해서 생기는 누적값이 정답이다.

 

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
using namespace std;
const int MAX = 4000;
int arr[4][MAX];
int AB[MAX * MAX], CD[MAX * MAX];


int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 4; j++)
			cin >> arr[j][i];
	}
	
	int idx = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			AB[idx] = arr[0][i] + arr[1][j];
			CD[idx] = arr[2][i] + arr[3][j];
			idx++;
		}
	}
	sort(AB, AB + idx);
	sort(CD, CD + idx);
	int AB_idx = 0;
	int CD_idx = idx - 1;
	long long ans = 0;
	while (AB_idx < idx && CD_idx >= 0)
	{
		if (AB[AB_idx] + CD[CD_idx] == 0)
		{
			long long AB_cnt = 0;
			int tem_AB_idx = AB_idx;
			while (AB[AB_idx] + CD[CD_idx] == 0)
			{
				AB_cnt++;
				AB_idx++;
				if (AB_idx >= idx)
					break;
			}

			long long CD_cnt = 0;
			while (AB[tem_AB_idx] + CD[CD_idx] == 0)
			{
				CD_cnt++;
				CD_idx--;
				if (CD_idx < 0)
					break;
			}
			ans += AB_cnt * CD_cnt;
		}
		else if (AB[AB_idx] + CD[CD_idx] < 0)
			AB_idx++;
		else
			CD_idx--;
	}
	cout << ans << endl;
}