[백준문제풀이] 7453 합이 0인 네 정수

 

풀이일시 : 2020-12-26

 

 

문제 : 

정수로 이루어진 크기가 같은 배열 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이다.

ex)

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

 

 

출력 : 

합이 0이 되는 쌍의 개수를 출력한다.

 

 

풀이 : 

투포인터 알고리즘으로 풀이할 수 있다.

 

입력을 arr[j][i] 로 주고, 0번째 열과 1번째 열을 합한 값을 ab vector에 2,3번째 열 합한것을 cd vector에 넣어준다.

 

투포인터 알고리즘을 사용하기 위해 ab와 cd vector 를 sort 해준다. (ab는 오름차순으로 cd는 내림차순으로)

 

이어 투포인터 알고리즘을 사용해준다.

 

dbstndi6316.tistory.com/39

[개념정리] Two pointer algorithm

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 4000;

int n;
int arr[4][MAX];
vector <int> ab;
vector <int> cd;
long long int c = 0, c1 = 0, c2 = 0;

void hap() { //ab를 합친것과 cd를 합친 백터 생성
	int cnt1=0,cnt2=0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			ab.push_back(arr[0][i] + arr[1][j]);
			cd.push_back(arr[2][i] + arr[3][j]);
		}
	}
}

void twopointer() {
	int check1 = 0;
	int check2 = 0;
	while (check1!=ab.size() && check2!=cd.size()) {
		c1 = 0, c2 = 0;
		int result = ab[check1] + cd[check2];
		if (result == 0) {
			//같은수반복
			for (int t = ab[check1]; check1 < ab.size() && t == ab[check1]; check1++, c1++);
			for (int t = cd[check2]; check2 < cd.size() && t == cd[check2]; check2++, c2++);
			c += c1 * c2;
		}
		else if (result > 0) {
			check2++;
		}
		else
			check1++;
	}
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 4; j++) {
			cin >> arr[j][i];
		}
	}
	hap();
	
	//투포인터 위해 cd는 내림차순으로 정렬해준다.
	sort(ab.begin(), ab.end());
	sort(cd.begin(), cd.end(), greater<int>());

	twopointer();

	cout << c << endl;
	return 0;
}

 

참고자료 : vector

dbstndi6316.tistory.com/25

[개념정리] vector container

참고자료 : sort

dbstndi6316.tistory.com/21

[개념정리] STL라이브러리 - sort()1