백준 7453 네 수의 합 - 투 포인터 알고리즘

문제

정수로 이루어진 크기가 같은 배열 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이 되는 쌍의 개수를 출력한다.

 

 

---

1. 문제 해석

늘 그렇듯이 브루트 포스부터 생각해볼 수 있다. 

이 경우 합이 0이 되는지 안되는지 각 배열을 하나씩 탐색하면, N^4 꼴의 시간 복잡도가 나올 것이다. 

따라서 이것은 매우 비효율적이므로 바로 패스.

 

그 다음으로 생각해볼 것은 배열의 합은 어차피 구해야 하는 것이므로, 

두 배열씩 더한 값을 가지고 있다고 쳐볼 수 있다. 

그럼 여기서 시간 복잡도는 N^2일 것이고,

최대 연산 횟수는 4000*4000 = 16 * 10^6이다. 1억보다 작은 숫자 이므로 아직까지는 1초가량을 잡아먹는다.

 

그 다음으로는 만든 두 배열(A, B 배열을 더한 AB배열, C, D배열을 더한 CD배열을 탐색하면서 합이 0이 되는지 찾아볼 수 있다. 

이때 단순하게 이중 for문을 돌면 결국 브루트포스와 다름이 없는 시간복잡도가 나올 것이고, 

 

더 효율적으로 합이 0이 되는 경우를 세는 방법을 생각해보아야 한다. 

 

* 어떤 두 수의 합이 0이 된다는 것은 한 수가 n일 때 다른 한 수는 -n 이라는 것을 의미한다. 

   -> 한 배열을 순회하면서 값이 n일 때 다른 배열에 -n값이 있는지 이분 탐색으로 조회한다. (nlogn 시간복잡도 추가) 

 

 

* 어떤 두 수의 연산 혹은 조건이 맞는 두 수 간의 간격을 셀 때, 투 포인터 알고리즘(일명 슬라이딩 윈도우)을 사용할 수 있다.

: 오름차순으로 정렬된 배열에서 한 포인터(low)는 가장 왼쪽, 다른 한 포인터(high)는 가장 오른쪽에 위치한다고 해보자.

포인터가 가리키는 두 수의 합이 원하는 값 N보다 크다면 high를 감소시키고, N보다 작다면 low를 증가시켜서 

원하는 값에 근접하도록 만드는 것이 핵심이다. 

 

이 게시글에서는 두 번째 방법, 투 포인터 알고리즘을 사용한 방법을 해설해보려고 한다.

 

 

문제에서 주어진 예시는 위와 같다. 

 

그리고 왼쪽부터 A, B, C, D 배열이 주어졌다고 할 때 ,

 

A , B 배열의 합을 AB 배열에 저장하고

C, D  배열의 합을 CD 배열에 저장한 다음

오름 차순으로 정리해보았다.

 

아래 적은 빨간색 글씨를 따라가보자. 

 

여기서 생각해보면 Low는 0, high는 35부터 시작한다. 

둘의 합 sum이 현재 34이다. 

그러면 원하는 0보다 훨씬 크므로,  큰 값을 더한 부분에서 값을 줄여봐야 한다. 

따라서 high를 34로 감소시킨다. -> sum  = 20 

 

이것을 반복하면서 high를 감소시키다보면, high가 30일 때 sum = -12로 0보다 작은 값이 나온다. 

 

음수가되었으므로 이번에는 low가 증가해서 1이 된다. 그러다가 증가해서 2, 3,..  4가 되면  AB의 값이 -86, 이때 

CD(high = 30)의 값이 87이고, 0보다 크기 때문에 high = 29로 감소한 순간,

CD의 값이 86이 되므로 처음으로 합이 0이 된다.

 

그럼 드디어 한 케이스를 찾은 것이다!

 

2.  주의점

위 방법처럼 하면 경우의 수를 모두 알아낸 것 같지만, 사실 중복값이 고려되지 않았다. 

AB가 -86, -86 이었고 CD가 86, 86이었다면 이때는 조합해서 경우의 수가 4가 된다. 

따라서 우리가 해주어야 하는 것은, 합이 0인 순간을 찾았을 때, 그 숫자로 만들 수 있는 경우의 수를 모두 찾아내야한다.

 

이는 배열에 같은 값이 몇 개 있는지 센 다음 곱해주는 것으로 치환하여 생각할 수 있다. 

이를 구현하기 위해서, 합이 0인 것으로 찾아낸 순간, 

같은 값을 만날 때까지 tlow, thigh라는 변수가 개수를 세도록 코드를 설계하였다. 

 

 

 

3. 구현

그리하여 구현한 코드는 다음과 같다. 

 

#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>

//첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.
using namespace std;
vector <int> nums;
#define MAX  4001
int N;
vector <int> A;
vector <int> B;
vector <int> C;
vector <int> D;
vector <long long> AB;
vector <long long> CD;

void make_array()
{
	long long ret = 0;
	long long  ans = 0;
	//AB의 합 저장, CD의 합 저장
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			AB.push_back(A[i] + B[j]);
			CD.push_back(C[i] + D[j]);
		}
	}
	//AB, CD 정렬 : 이진탐색을 위해
	//AB의 값에 대해 그 반대 부호의 값이 CD에 있는지 그 개수를 이진탐색 수행.   <- 중복되었을 떄 이진탐색?
	sort(AB.begin(), AB.end());
	sort(CD.begin(), CD.end());
	

}

long long find_zero()
{
	make_array();
	long long low = 0, high = N * N - 1, ans = 0;
	long long tl, th;
	while(low < N*N && high >= 0)
	{
		if (AB[low] + CD[high] == 0)
		{
			tl = low;
			while (low < N*N && AB[tl] == AB[low])
				low++;
			th = high;
			while (high >= 0 && CD[th] == CD[high])
				high--;
			ans += (low - tl) * (th - high);
		}
		else if (AB[low] + CD[high] > 0)
			high--;
		else
			low++;
	}
	return ans;
}

void input() {
	int a, b, c, d;
	for (int i = 0; i < N; i++)
	{
		cin >> a >> b >> c >> d;
		A.push_back(a);
		B.push_back(b);
		C.push_back(c);
		D.push_back(d);
	}
}

int main()
{
	cin >> N;
	input();
	cout << find_zero() << "\n";
}