BOJ 7453 - 합이 0인 네 정수

• N(1<=N<=4000)개의 정수로 이루어진 배열 A, B, C, D가 주어질 때 A[a]+B[b]+C[c]+D[d]=0인 (a, b, c, d)의 개수를 구하는 문제이다.

문제 풀이

• (a, b, c, d)를 Brute-force로 구하려면 O(4000^4)가 걸리는데 이건 TLE기 때문에 A+B, C+D를 계산해서 16000000길이의 배열 두 개(AB, CD)로 바꾸고 AB[i]+CD[j]=0이 되는 (i, j)를 효율적으로(제곱 이하의 시간이 들게) 찾아야 한다.

• 나는 upper_bound, lower_bound를 이용해서 binary search를 두 번 하는 방식으로 풀었다. CD를 정렬한 후 CD에서 S-AB의 개수를 위의 탐색 두 번으로 찾는 것이다. 이것만 해도 시간복잡도가 O(NlgN)이기 때문에 AC를 받는다.(첫 번째 코드) 하지만 정답자들의 코드를 둘러보면서 더 다양한 방법들을 찾을 수 있었다.

  • Radix sort 이용
    AB를 기수정렬(Radix sort)를 통해 AB, CD를 더 빠르게 정렬 후 Two pointers처럼 AB는 처음부터, CD는 마지막부터 sweeping하면서 두 원소의 합을 체크하는 것이다.(sum>0이면 CD의 포인터 감소, sum<0이면 AB의 포인터 증가) 이 경우 비교하는 방법이 Two pointers와 비슷하게 O(2N)이 들기 때문에 기수정렬의 시간복잡도 O(dN)이 전체 O(n)을 지배한다. 기수정렬은 구현하지 않고 STL의 sort를 이용하고 합치는 방법만 구현해보았는데(두 번째 코드) 첫 번째보다 확실히 더 빨랐다.

  • hashing 이용
    이 문제도 사실 AB, CD로 합친 뒤에 이 배열들의 값을 인덱스로 사용할 수 있다면 O(16000000)만에 해결할 수 있다. 하지만 배열의 값이 최대 2^28까지기때문에 메모리제한으로 걸리게된다. 하지만 hashing을 이용하면 사용하는 메모리를 줄일 수 있다. 직접 구현해보진 않았지만 정답자들의 코드를 보면 해시함수를 잘 설계하면 대략 300ms정도로 풀리는 것 같다.

소스코드

// //binary search, 1524ms
// #include<bits/stdc++.h>
// using namespace std;
// typedef vector<int> vi;

// int main()
// {
// 	ios::sync_with_stdio(false);cin.tie(0);
// 	int n, a[4000], b[4000], c[4000], d[4000];
// 	long long cnt=0;
// 	vi vab;
// 	cin>>n;
// 	for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
// 	for(int i=0;i<n;i++) for(int j=0;j<n;j++)
// 		vab.push_back(a[i]+b[j]);
// 	sort(vab.begin(), vab.end());
// 	for(int i=0;i<n;i++) for(int j=0;j<n;j++){
// 		int ps=c[i]+d[j];
// 		cnt+=upper_bound(vab.begin(), vab.end(), -ps)-lower_bound(vab.begin(), vab.end(), -ps);
// 	}
// 	cout<<cnt;
// }

//Two pointers, 952ms
#include<bits/stdc++.h>
using namespace std;
int n, abi=1, a[4000], b[4000], c[4000], d[4000], ab[16000002], cd[16000001];
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	long long cnt=0;
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i]>>b[i]>>c[i]>>d[i];
	for(int i=0;i<n;i++) for(int j=0;j<n;j++){
		ab[abi]=a[i]+b[j];
		cd[abi++]=c[i]+d[j];
	}
	sort(ab+1, ab+abi);
	sort(cd+1, cd+abi);
	ab[abi]=300000000;
	cd[0]=-300000000;
	int i=1, j=abi-1, sum=ab[i]+cd[j];
	while(i<abi && j>0){
		if(sum==0){
			long long abn=1, cdn=1;
			while(ab[i]==ab[++i]) abn++;
			while(cd[j]==cd[--j]) cdn++;
			cnt+=abn*cdn;
			sum=ab[i]+cd[j];
		}
		else if(sum>0) while(sum>0) sum=ab[i]+cd[--j];
		else while(sum<0) sum=ab[++i]+cd[j];
	}
	cout<<cnt;
}

풀고나서

• Hashing의 Collision Resolution으로 Open addressing, Chaining이 있는데, Load factor(Data/Storage*100)가 대략 75%를 넘어가면 재탐사 횟수가 급격히 증가하면서 Open addressing의 성능이 지수적으로 떨어지게 된다. 따라서 Open addressing을 쓸 경우 hash table의 사이즈를 데이터 크기(16000000)보다 더 크게 잡아야 한다.

• Chaining을 사용할 경우는 처음 정한 hash table 사이즈보다 최대 데이터 크기만큼의 공간이 더 필요할 수 있지만 Load factor에 대해 선형적으로 실행시간이 증가한다. 따라서 저장공간이 충분히 큰 경우 구현이 쉬운 Open addressing을 사용하는 것이 편하지만 데이터를 짐작할 수 없을 때 같은 일반적인 경우 Chaining을 사용하는 것이 좋다.
  [BOJ] 백준 7453 합이 0인 네 정수 여기서도 Open addressing을 사용할 때 해시 테이블의 크기를 데이터의 크기(16000000)보다 충분히 크게(30000000) 잡는 것을 볼 수 있다.