[백준] 7453번: 합이 0인 네 정수 - Hash

문제

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

7453번: 합이 0인 네 정수

 

문제해결

Hash 기법 사용

STL unordered_map을 사용하면 시간 초과 발생하여, 직접 구현이 필요합니다.

Hash 함수가 어느 정도 분배가 보장되도록 설계한다면 시간 제한에 여유 있게 통과 가능합니다.

Chaining 방법과 Open addressing(liner probing 등) 모두 가능하다.

 

결과

1. STL 사용시

: 대부분 시간 초과이며, 통과되었을 때도 메모리/시간 사용량이 크다

2. Hash Chaining 버전
: STL 사용할 때보다 메모리/시간 사용량이 절반이다.

3. Hash Open addressing(Linear Probing)

시간 초과...

linear probing에서는 군집화(clustering) 발생이 탐색을 저해하는 요인이다.

코드에서 SIZE 변수의 값을 조절해야 통과가 될 것 같다..ㅠ

코드

1. stl unordered_map 사용

#include<iostream>
#include<unordered_map>
using namespace std;

using ll = long long;

int N;
int A[4005], B[4005], C[4005], D[4005];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;

	for (int i = 0; i < N; i++)
	{
		cin >> A[i] >> B[i] >> C[i] >> D[i];
	}

	unordered_map<int, ll> um;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			um[A[i] + B[j]]++;
		}
	}

	ll ans = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (um.count(-(C[i] + D[j])) != 0)
				ans += um[-(C[i] + D[j])];
		}
	}
	cout << ans;
	return 0;
}

2. Hash 구현 - Chaining 기법

#include<iostream>
using namespace std;

using UI = unsigned int;
const int LM = 4005;
const int SIZE = 1 << 24;
const int MOD = SIZE - 1;
int n, a[LM], b[LM], c[LM], d[LM];
long long ans;

struct Node
{
	UI key, cnt;
	Node* next;
	Node* alloc(UI nk, Node* np)
	{
		key = nk, cnt = 1, next = np;
		return this;
	}
}buf[LM*LM+10],*htab[SIZE];
int bcnt;

Node* probing(UI key, int hidx)
{
	for (Node* p = htab[hidx];p; p = p->next)
	{
		if (p->key == key) return p;
	}
	return NULL;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(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++)
		{
			UI key = a[i] + b[j];
			int hidx = key & MOD;
			Node* p = probing(key, hidx);
			if (p)p->cnt++;
			else htab[hidx] = buf[bcnt++].alloc(key, htab[hidx]);
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			UI key = -(c[i] + d[j]);
			Node* p = probing(key, key & MOD);
			if (p) ans += p->cnt;
		}
	}
	cout << ans;
	return 0;
}

3. Hash 구현 - Open addressing(Linear Probing)

#include<iostream>
using namespace std;

const int LM = 4000;
using UI = unsigned int;

const int SIZE = 29999999;
int n, a[LM], b[LM], c[LM], d[LM];
int htab[SIZE], cnt[SIZE];
long long ans;

int hashFunction(UI sum)
{
	return sum % SIZE;
}

int probing(int hidx, int newKey)
{
	for (int i = hidx;; i = (i + 1) % SIZE)
	{
		if (cnt[i] == 0 || htab[i] == newKey)
			return i;
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(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++)
		{
			int key = a[i] + b[j];
			int hidx = hashFunction(key);
			hidx = probing(hidx, key);
			if (cnt[hidx] == 0) htab[hidx] = key;
			cnt[hidx]++;
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int key= - (c[i] + d[j]);
			int hidx = hashFunction(key);
			hidx = probing(hidx, key);
			ans += cnt[hidx];
		}
	}
	cout << ans;
	return 0;
}