[백준] | C++ | 7453. 합이 0인 네 정수 (unordered_map, 해시 충돌)

개요

solved.ac 클래스 5 문제 탐색 도중 제목이 제일 만만해 보여서 고른 문제입니다.

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이 되는 쌍의 개수를 출력한다.

 

테스트 케이스

입력	출력
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	5

 

 

---

 

 

풀이

알고리즘 분류는 예상했듯이 이분 탐색에 두 포인터입니다.

근데... 중간에서 만나기?

조금 낯선 키워드가 하나 껴있죠.

 

중간에서 만나기는 브루트포스 등의 방법을 사용해야 하는데 범위가 매우 커졌을때 사용하는 방법입니다. 탐색을 n등분 하고 그 n등분한 탐색 결과를 다시 탐색하는 그런 방법인데 분할 정복이랑 살짝 비슷한 면이 있어요.

 

들어오는 A, B, C, D 배열을 전부 브루트포스로 탐색하게 되면 시간 복잡도가 \(O(n^4)\)로 n이 최대 4000까지 들어오니 대강 256,000,000,000,000 정도라서 시간 제한(12초)을 한참 초과합니다.

그러니 배열을 나눠서 탐색을 해야겠죠.

 

아이디어 정리

제 아이디어는 다음 두 식에서 도출됩니다.

$$A[a] + B[b] + C[c] + D[d] = 0$$

$$A[a] + B[b] = -(C[c] + D[d])$$

 

\(A[a] + B[b]\)가 \(-(C[c] + D[d])\)와 같다면 4개를 합친 몫은 0이 되겠죠? 그러니 A와 B 배열을 탐색하면서 가능한 합연산의 몫을 모두 구합니다. 최대로 \(n^2\)개 정도 나올 수 있습니다.

 

그리고 다시 C와 D 배열을 탐색하면서 가능한 합연산의 몫을 모두 구합니다. 얘도 마찬가지로 최대 \(n^2\)개 까지 나와요.

 

그리고 뽑아낸 AB의 합과 와 CD의 합 배열을 정렬한 후 하나는 0부터 하나는 n*n 부터 탐색을 하면 됩니다.

이분 탐색에 두 포인터인데 그 포인터가 한 배열이 아니라 2개에 배열에 각각 떨어져 있는 느낌이죠.

일단 시간 복잡도를 대강 계산 했을 때 \(O(n^2 log n)\) 정도가 나옵니다.

 

 

...근데 이거 조금 맘에 안들어요. 굳이 합연산 배열을 2개 만들어서 또 다시 탐색할 필욘 없을 것 같습니다. 그래서 저는 map을 사용하기로 했어요.

 

일단 A와 B 배열을 탐색하면서 가능한 합연산의 몫을 모두 구합니다. 여기까진 똑같죠.

근데 이제 map을 사용해서 나온 몫에 개수를 캐싱합니다.

std::unordered_map<int, int> map
map[A + B]++;

Key의 합연산의 값을 넣고 Value엔 그 값이 나온 횟수를 넣는 것이죠.

 

그리고 이제 C와 D 배열을 탐색하면서 가능한 합연산의 몫을 모두 구해요. 근데 배열에 캐싱하는 대신 map에 Key로 집어 넣습니다.

근데 위에서 말했듯이 \(A[a] + B[b] = -(C[c] + D[d])\) 라면 \(A[a] + B[b] + C[c] + D[d] = 0\)죠.

그러니 다음과 같이 값을 찾습니다.

int cnt = 0;
cnt += map[-(C + D)]

 

이렇게 하면 시간 복잡도 \(O(n^2)\)만에 해결이 가능합니다.

 

 

코드로 풀기

아이디어가 다 나왔다면 코드로 푸는 것은 간단합니다.

일단 전 백준 문제 풀때 define을 쓰는 것을 즐기기 때문에 간단하게 define 몇개만 선언하고 갑시다.

#define A 0
#define B 1
#define C 2
#define D 3

 

 

그 뒤에 인풋 형식에 맞게 vector를 선언하고 값을 입력 받습니다.

int n;
cin >> n;

vector<vector<int>> numVec(D + 1, vector<int>(n));

for (int i = 0; i < n; i++)
{
	for (int j = A; j <= D; j++)
	{
		cin >> numVec[j][i];
	}
}

 

 

입력을 전부 받았으니 이제 A와 B 배열을 돌면서 가능한 합연산을 모두 구하고 그것을 unordered_map에 집어넣습니다.

std::unordered_map<int, int> sumAB;

for (int i = 0; i < n; i++) 
{
	for (int j = 0; j < n; j++) 
	{
		int sum = numVec[A][i] + numVec[B][j];
		sumAB[sum]++;
	}
}

똑같은 값이 또 나오면 그건 이제 map에 누적해서 들어갑니다.

 

 

그리고 C와 D 배열을 돌면서 가능한 합연산을 구합니다. 그리고 그 합에 -1을 곱하고 map에 Key로 집어넣으면 나오는 값을 count 변수에 모두 더해주면 됩니다.

size_t count = 0;
for (int i = 0; i < n; i++) 
{
	for (int j = 0; j < n; j++) 
	{
		int sum = numVec[C][i] + numVec[D][j];
		count += sumAB[-sum];
	}
}

 

count를 size_t로 둔 이유는 모든 입력이 0이 들어오면 \(n^4\)까지 count가 올라가기 때문입니다. n이 4000까지니까 \(4000^4\)이면 int로는 거들떠볼 수도 없는 값이 나옵니다.

 

 

근데 이렇게 하면...

메모리 초과가 발생합니다.

 

 

이유를 알아보니 C와 D를 탐색할때 unordered_map에 -sum이 Key인 값을 찾고 있는데 -sum인 Key가 존재하지 않으면 unordered_map에 -sum이 Key인 pair를 하나 더 만들기 때문에 메모리 초과가 발생할 수 밖에 없더군요. 그래서 로직을 수정해주겠습니다.

 

이러면 되겠죠.

size_t count = 0;
for (int i = 0; i < n; i++) 
{
	for (int j = 0; j < n; j++) 
	{
		int sum = numVec[C][i] + numVec[D][j];
		auto it = sumAB.find(-sum);
		if (it != sumAB.end()) 
		{
			count += it->second;
		}
	}
}

 

이제 시간 복잡도도 \(O(n^2)\)에 메모리도 낭비하지 않는 완벽한 풀이라고 생각했습니다.

??;;;

 

 

시간 초과는 예상치 못했습니다. unordered_map은 해시 테이블 기반이라 접근이 \(O(1)\)이라서 충분히 될 줄 알았는데요...

생각을 해보면 unordered_map에서 해시 충돌이 발생할 경우 Key 기반 접근의 시간 복잡도가 \(O(n)\)까지 증가할 수 있습니다. 그러니 unordered_map를 미리 reserve 해야했죠.

 

unordered_map의 reserve는 vector의 reserve와 비슷하면서도 다릅니다. 둘 다 미리 저장공간을 확보해놓는 것은 똑같지만 unordered_map은 해시 충돌이 나지 않도록 Key-Value Pair가 들어가는 Bucket이란 것을 미리 확보해둡니다. 이 Bucket이 적을 경우 Pair가 똑같은 Bucket에 들어갈 가능성이 증가하니 해시 충돌이 발생하는겁니다. 그래서 미리 Bucket을 많이 만들어두는 것이죠.

 

아무튼 이런식으로 reserve를 하면...

std::unordered_map<int, int> sumAB;
sumAB.reserve(n * n);

 

 

 

진짜 성공입니다.

 

 

 

---

 

 

 

마치는 말

접근 자체는 잘했는데 unordered_map의 특성을 여럿 놓쳐서 아쉬웠던 풀이입니다. 그래도 학습이 되었으니 OK 입니다.

 

 

코드 전문

#define FAST_PRINT std::ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)

#define BEGIN_TO_END(vec) vec.begin(), vec.end()
#define A 0
#define B 1
#define C 2
#define D 3

int main()
{
	FAST_PRINT;

	int n;
	cin >> n;

	vector<vector<int>> numVec(D + 1, vector<int>(n));

	for (int i = 0; i < n; i++)
	{
		for (int j = A; j <= D; j++)
		{
			cin >> numVec[j][i];
		}
	}

	std::unordered_map<int, int> sumAB;
	sumAB.reserve(n * n);

	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < n; j++) 
		{
			int sum = numVec[A][i] + numVec[B][j];
			sumAB[sum]++;
		}
	}

	size_t count = 0;
	for (int i = 0; i < n; i++) 
	{
		for (int j = 0; j < n; j++) 
		{
			int sum = numVec[C][i] + numVec[D][j];
			auto it = sumAB.find(-sum);
			if (it != sumAB.end()) 
			{
				count += it->second;
			}
		}
	}

	cout << count;
}