7453 four Integer’s sum should be zero
알고리즘(정렬, 이분탐색)
1
2
3
4
5
1. 앞 두개 정수의 합 배열, 뒤 두개 정수의 합 배열을 만듬.(배열 개수^2 가 합 배열의 길이)
2. 두 배열을 정렬
3. 앞 합 배열의 원소를 하나씩 빼며 검사 -> 뒤 합 배열에서, upper_bound - lower_bound 값이, 현재 원소에서의 count 값.
4. count 를 더하고 다음 원소 검사
5. count 값을 long long 으로 선언
구현
1
1. lower_bound, upper_bound 로 몇개있는지 구하고, 그걸 count 에 더하는 식으로 구현
더 빠른 방법
1
2
3
4
5
6
7
8
1. 합 배열에 중복된 값이 들어가는 게 문제.
2. 구조체를 선언하고, 합과, 그 합이 몇번 나왔는지 저장하는 방법
-> 먼저 합 배열을 만들고, 같은 값이 나올 때마다, 같은 값의 가장 앞에 있는 곳에 count를 하나씩 증가하고 뒤에있는 같은 값은 sum을 -1로 만들어 버린다.
-> 그리고 값이 달라질때마다 count를 1씩 증가하여, 압축한 길이가 몇인지 구하기.
-> 값을 찾을 때는 이분탐색으로 찾는다.
3. 앞보단 느리지만, 앞 합배열의 원소를 꺼낼때, 같은 원소면 바로 통과하도록 하기
-> 앞에서 연산한 결과를 이용하여 바로 통과시키자.
-> 130ms 줄임
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <algorithm>
#define MAX_ARRAY 4000
using namespace std;
int intArray[MAX_ARRAY][4];
int firstTwo[MAX_ARRAY*MAX_ARRAY], lastTwo[MAX_ARRAY * MAX_ARRAY];
int numOfArray;
void generateSum();
long long getCount();
int main() {
cin >> numOfArray;
for (int i = 0; i < numOfArray; i++) {
for (int j = 0; j < 4; j++)
cin >> intArray[i][j];
}
generateSum();
sort(firstTwo, firstTwo + numOfArray*numOfArray);
sort(lastTwo, lastTwo + numOfArray*numOfArray);
cout << getCount();
}
void generateSum() {
int index = 0;
for (int i = 0; i < numOfArray; i++) {
for (int j = 0; j < numOfArray; j++) {
firstTwo[index] = intArray[i][0] + intArray[j][1];
lastTwo[index++] = intArray[i][2] + intArray[j][3];
}
}
}
long long getCount() {
long long count = 0;
int save[2] = { -1,-1 };
for (int i = 0; i < numOfArray*numOfArray; i++) {
int temp;
if (save[0] == firstTwo[i])
temp = save[1];
else
temp = (upper_bound(lastTwo, lastTwo + numOfArray * numOfArray, 0 - firstTwo[i])
- lower_bound(lastTwo, lastTwo + numOfArray * numOfArray, 0 - firstTwo[i]));
save[0] = firstTwo[i];
save[1] = temp;
count += temp;
}
return count;
}