[백준] 7453번 : 합이 0인 네 정수

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

문제

알고리즘 접근 방법

정수로 이루어진 크기가 같은 배열 A, B, C< D
A[a]+B[b]+C[c]+D[d]의 합이 0인 (a, b, c, d) 쌍의 개수
각 배열의 최대 크기 = 4000

Brute force 로 풀면(막 풀면) 400040004000*4000

배열이 2개라면?
A+B의 합이 0이 되도록 계산하는 방법
-> A, B를 정렬한다면?

2-pointer 이용
하나는 맨 앞, 하나는 맨 끝

O(NlogN)으로 해결

4개의 배열을 2개의 배열로 만들 수 있을까?
A+B의 경우를 모두 계산 > 4000 4000 개
CD의 경우를 모두 계산 > 4000 * 4000 개
16,000,000개의 배열 2개가 만들어짐 > 시간복잡도 O(N^2)

풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long A[4000];
long long B[4000];
long long C[4000];
long long D[4000];
vector<long long> AB;
vector<long long> CD;

int main(){

    int n;
    cin >> n;

    for(int i=0; i<n; i++){
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            AB.push_back(A[i]+B[j]);
            CD.push_back(C[i]+D[j]);
        }
    }

    sort(AB.begin(), AB.end());
    sort(CD.begin(), CD.end());

    long long start = 0, end = AB.size()-1; //2 pointer
    long long result = 0, sum;
    int before_end;
    while(start < AB.size() && end >= 0){
        sum = AB[start] + CD[end] ;
        if (sum>0) end--; 
        else if (sum == 0){
            // 같은거 세기
            long long ab = 1, cd = 1;
            while (start < AB.size() - 1 && AB[start] == AB[start + 1]) {
                start++;
                ab++;
            }
            while (end > 0 && CD[end] == CD[end-1]) {
                end--;
                cd++;
            }
            result += ab*cd;
            start++;
        }
        else start++;
        
    }

    cout << result << '\n';
    return 0;
}

정리

으아 오래걸렸따
투 포인터는 이제 알겠는데
같은 거 있을 때가 예외경우였다!

💡 참고 포스팅

7453 합이 0이 되는 네 정수 반례 하나만 부탁드립니다 (C++)
비😶님 블로그