[G2] 백준 7453번 합이 0인 네 정수 C++ 이분 탐색, 투 포인터, upper_bound, lower_bound, 정렬

리뷰

 

하 너무 어려웠던 지옥같은 문제, 투 포인터 문제중에선 골드 2치고 굉장히 어려웠다.

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

 

문제 풀이

1. a, b, c, d배열에 값을 받아 줄 abcd를 최대치의 크기 4000 * 4의 크기로 전역 변수로 설정해 준다.
2. ab와 cd 배열을 합칠 벡터 ab, cd와 정답을 저장할 변수 ans를 long long타입으로 전역 변수로 설정해 준다.
3. n값을 입력 받고 n * 4 크기의 배열을 abcd 배열에 입력받아 저장해 준다.
4. n * n크기의 브루트포스를 통해 각 경우의 수를 찾아 a + b는 ab에, c + d는 cd에 저장해 준다.
5. ab와 cd 배열을 모두 오름차순으로 정렬해 준 후 투 포인터 탐색을 시작해 준다.
6. p1은 ab벡터의 포인터로 0부터 시작한다, p2는 cd벡터의 포인터로 n * n - 1부터 시작해 준다.
7. p1과 p2가 범위를 벗어나지 않을 때 까지 탐색을 진행한다, sum변수에 ab[p1] + cd[p2]값을 받아준다.
8. 만약 sum이 0보다 크다면 p2를 줄여 값을 0에 가깝게 만들어 준다, 반대의 경우 p1을 증가시켜 준다.
9. 만약 sum이 0이라면 ab벡터에서는 현재보다 큰 값이 나온 인덱스를 찾아 it1에 받아준다.
10. cd벡터에서는 현재값과 동일한 값이 나온 인덱스를 찾아 it2에 받아준다.
11. cnt1에 it1의 인덱스를, cnt2에 it2의 인덱스를 저장해 준 뒤 ans에 동일한 값의 경우를 곱해 더해줄 것이다.
12. 우선 cnt1은 p1보다 항상 크기때문에 cnt1 - p1을 해준다, cnt2는 p2보다 항상 작거나 같기 때문에 p2 - cnt2 + 1
13. 두 값을 곱한 뒤 ans에 더해주면 동일한 숫자의 쌍은 모두 한번에 처리가 가능하다.
14. 이후 p1은 cnt1로, p2는 cnt2에서 -1한 값으로 설정해 준다. 탐색이 종료된 후 ans를 출력해 주면 된다.

 

 

참고 사항

upper_bound는 입력한 수보다 큰 값을 찾으면 해당 위치의 이터레이터를 반환한다. 따라서 it1은 항상 p1보다 클 수 밖에 없다, it1의 위치에서 p1을 빼준다면 ab[p1]과 동일한 숫자의 개수를 알 수 있다.

lower_bound는 입력한 수 이상인 값을 찾으면 해당 위치의 이터레이터를 반환한다. 따라서 it2는 항상 p2보다 작거나 같다. it2의 위치에서 p2를 빼준다면 cd[p2]과 동일한 숫자의 개수를 알 수 있다.

하지만 동일한 숫자가 한개도 없을 경우 자기 자신의 위치를 반환하기 때문에 +1을 해주어야 정확한 개수가 나온다.

 

정답 코드에서 주석처리가 되어있는 방식으로도 동일하게 같은 숫자의 개수를 찾을 수 있다.

하지만 O(N)의 시간 복잡도가 소요되므로 O(LogN)의 시간복잡도를 같는 upper_bound, lower_bound를 통한 탐색이 더 유리하다.

 

 

정답 코드

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long

using namespace std;

int abcd[4000][4];
vector<int> ab, cd;
ll ans = 0;

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

	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> abcd[i][j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ab.push_back(abcd[i][0] + abcd[j][1]);
			cd.push_back(abcd[i][2] + abcd[j][3]);
		}
	}

	sort(ab.begin(), ab.end());
	sort(cd.begin(), cd.end());

	ll p1 = 0, p2 = n * n - 1;
	while (p1 < n * n && 0 <= p2) {
		int sum = ab[p1] + cd[p2];
		if (sum > 0) p2--;
		else if (sum < 0) p1++;
		else {
			auto it1 = upper_bound(ab.begin(), ab.end(), ab[p1]);
			auto it2 = lower_bound(cd.begin(), cd.end(), cd[p2]);
			ll cnt1 = it1 - ab.begin();
			ll cnt2 = it2 - cd.begin();
			//long long cnt1 = 1, cnt2 = 1;
			//while (p1 + cnt1 < n * n && ab[p1 + cnt1] == ab[p1]) cnt1++;
			//while (p2 - cnt2 >= 0 && cd[p2 - cnt2] == cd[p2]) cnt2++;
			ans += (cnt1 - p1) * (p2 - cnt2 + 1);
			p1 = cnt1;
			p2 = cnt2 - 1;
		}
	}
	cout << ans;
}