[BOJ] 합이 0인 네 정수 7453번 C++

문제

정수로 이루어진 크기가 같은 배열 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이 되는 쌍의 개수를 출력한다.

 

접근 방식

 

은근 투 포인터 문제에 map 자료구조를 사용하는 풀이가 많이 있는 것 같다

해당 문제는 AB의 합을 unordered_map에 저장(map에 저장하면 매번 sort가 일어나기 때문에 시간초과 발생)

하고 C,D 배열을 돌면서 해당하는 값이 존재하는지 확인만 하면 된다!

 

 

코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector<int> A(n), B(n), C(n), D(n);
    for(int i = 0; i < n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }

    unordered_map<int, int> ABsums;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            ABsums[A[i] + B[j]]++;
        }
    }

    long long ans = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            int sumCD = C[i] + D[j];
            if(ABsums.find(-sumCD) != ABsums.end()) {
                ans += ABsums[-sumCD];
            }
        }
    }

    cout << ans;
    return 0;
}