[이분탐색] 백준 7453 :: 합이 0인 네 정수

합이 0인 네 정수 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	256 MB	7483	1597	947	20.196%

문제

정수로 이루어진 크기가 같은 배열 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에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 2²⁸이다.

출력

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

예제 입력 1 

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

예제 출력 1 

5

 

 문제 풀이

1차 풀이 (  126924 KB,  1264 ms)

• 배열을 두개씩 묶자
  A와 B의 요소를 각각 더한것을 AB.
  C와 D의 요소를 각각 더한것을 CD.
  
  
• 이분탐색으로 더해서 0이 되는 값을 찾자
  AB[i] + CD[j]를 만족하는 j를 찾자.
  CD에서 값이 -AB[i]인 원소의 개수만큼 더한다.

#include <iostream>
#include <algorithm>
using namespace std;
using int32 = int32_t;
using int64 = int64_t;


int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);


        //! 데이터 받기.
        int32 N;
        cin >> N;
        int32 A[N], B[N], C[N], D[N];
        for(int32 i=0; i<N; i++){
                cin >> A[i] >> B[i] >> C[i] >> D[i];
        }


        //! 데이터 취합 후, 정렬.
        int32 NSquare = N*N;
        int32 X[NSquare], Y[NSquare];
        for(int32 i=0; i<N; i++){
                for(int32 j=0; j<N; j++){
                        X[i*N + j] = A[i] + B[j];
                        Y[i*N + j] = C[i] + D[j];
                }
        }
        sort(Y, Y+NSquare);


        //! X[i] == -Y[j] 를 만족하는 j를 구한다.
        int64 ret = 0;
        int32 *srt, *end;
        for(int32 i=0; i<NSquare; i++){
                srt = lower_bound(Y, Y+NSquare, -X[i]);
                end = upper_bound(Y, Y+NSquare, -X[i]);
                if(srt == end) continue;
                ret += end - srt;
        }
        cout << ret << '\n';
}

2차 풀이 (  126928 KB,  1076 ms)

• 이분탐색의 범위를 계속 줄이자
  AB와 CD가 정렬되어 있으므로,
  지나간 구간에서는 더해서 0이 되는 값이 나올 수 없다.
  지나간 구간은 탐색하지 않도록 한다.

#include <iostream>
#include <algorithm>
using namespace std;
using int32 = int32_t;
using int64 = int64_t;


int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);


        //! 데이터 받기.
        int32 N;
        cin >> N;
        int32 A[N], B[N], C[N], D[N];
        for(int32 i=0; i<N; i++){
                cin >> A[i] >> B[i] >> C[i] >> D[i];
        }


        //! 데이터 취합 후, 정렬.
        int32 NSquare = N*N;
        int32 X[NSquare], Y[NSquare];
        for(int32 i=0; i<N; i++){
                for(int32 j=0; j<N; j++){
                        X[i*N + j] = A[i] + B[j];
                        Y[i*N + j] = C[i] + D[j];
                }
        }
        sort(X, X+NSquare);
        sort(Y, Y+NSquare);


        //! X[i] == -Y[j] 를 만족하는 j를 구한다.
        int64 ret = 0;
        int32 *x_srt, *y_end;
        int32 *xs, *xe, *ys, *ye;

        x_srt = X;
        y_end = Y+NSquare;
        while(x_srt < X+NSquare && Y < y_end){
                xs = x_srt;
                xe = upper_bound(x_srt, X+NSquare, *x_srt);
                ys = lower_bound(Y, y_end, -(*x_srt));
                ye = upper_bound(Y, y_end, -(*x_srt));
                if(ys != ye) {
                        ret += (xe - xs) * (ye - ys);
                        y_end = ys;
                }
                x_srt = xe;
        }
        cout << ret << '\n';
}

3차 풀이 (  80112 KB,  268 ms)  <해시 테이블>

• 해시 테이블 삽입
  "AB"의 원소들을 해시테이블에 넣으면서, 값을 카운트한다.
  해싱 충돌이 발생한다면 다른 비어있는 칸을 찾는다.
  
  
• 해시 테이블 추출
  -"CD"의 원소들을 해시 테이블에서 찾는다.
  -CD가 해시 테이블에 존재한다면, AB의 원소중 +CD가 있다는 것이다.
  
  
• 맵은 안된다
  map,  hash_map은 내부적으로 트리형태를 이루고 있기 때문에 오버헤드가 많다.
  사용한다면 시간초과에 가까운 점수를 받게될 것 이다.
  직접 해시 테이블을 만들어서 사용하는 것이 최적이다.
  

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
using int32 = int32_t;
using int64 = int64_t;


const int32 SIZE = 10'000'000;
const int32 KEY  = SIZE/3;

int32 num[SIZE], cnt[SIZE];


void put(int32 val) {
        int32 idx = val % SIZE;
        while(true){
                idx = (idx + KEY) % SIZE;
                if(num[idx] == val || num[idx] == SIZE){
                        num[idx] = val;
                        cnt[idx]++;
                        return;
                }
        }
}

int get(int32 val) {
        int32 idx = val % SIZE;
        while(true){
                idx = (idx + KEY) % SIZE;
                if(num[idx] == SIZE) return 0;
                else if(num[idx] == val) return cnt[idx];
        }
}

int main() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);

        for(int32 i=0; i<SIZE; i++) num[i] = SIZE;
        memset(cnt, 0, sizeof cnt);

        //! 데이터 수신.
        int32 N;
        cin >> N;
        int32 A[N], B[N], C[N], D[N];
        for(int32 i=0; i<N; i++){
                cin >> A[i] >> B[i] >> C[i] >> D[i];
        }


        for(int32 i=0; i<N; i++){
                for(int32 j=0; j<N; j++){
                        put(A[i] + B[j]);
                }
        }

        int64 ret = 0;
        for(int32 i=0; i<N; i++){
                for(int32 j=0; j<N; j++){
                        ret += get(-C[i] -D[j]);
                }
        }
        cout << ret;
}