[백준 2143] 두 배열의 합

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

나는 투 포인터를 활용해서 풀었는데, 이진탐색을 사용해서 푼 사람들도 많았다.
시간복잡도는 거의 동일하니 편한 방법을 쓰면 될 것 같다.
소요 시간만 놓고 보면 투포인터가 조금 더 빠르게 찍혔는데, 코드 길이 생각하면 그냥 이진탐색 쓰고 말듯.
+ 해시맵 방법도 있어서 해봤는데 구현 속도도, 시간복잡도도 이진탐색이 좋은 것 같다.

시간 복잡도

O($n^2 logm$)
-> 아래에서 자세히 설명

투 포인터

풀이 과정

1. A부분합과 B부분합을 모두 구한다.
2. A부분합을 오름차순, B부분합을 내림차순 한다.
3. A부분합+B부분합이 t가 되는 경우를 구한다.
4. 만약 t가 된다면 t가 되는 A부분합의 개수 * B 부분합의 개수를 count에 더한다.
   • 경우의 수를 구하는 것 이기 때문
5. 만약 t보다 크다면 B부분합의 idx--, t보다 작다면 A부분합의 idx++

구현

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int T, n, m;
    cin >> T >> n;
    
    int A[1000];
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    cin >> m;
    int B[1000];
    for (int i = 0; i < m; i++) {
        cin >> B[i];
    }
    
    // A의 모든 부분 배열의 합 계산
    vector<int> sumA;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += A[j];
            sumA.push_back(current_sum);
        }
    }

    // B의 모든 부분 배열의 합 계산
    vector<int> sumB;
    for (int i = 0; i < m; i++) {
        int current_sum = 0;
        for (int j = i; j < m; j++) {
            current_sum += B[j];
            sumB.push_back(current_sum);
        }
    }

    // sumA는 오름차순, sumB는 내림차순으로 정렬
    sort(sumA.begin(), sumA.end());
    sort(sumB.begin(), sumB.end(), greater<int>());

    long long count = 0;
    int i = 0, j = 0;

    // 투 포인터를 이용한 두 리스트의 합 비교
    while (i < sumA.size() && j < sumB.size()) {
        int a = sumA[i];
        int b = sumB[j];
        int sum = a + b;

        if (sum == T) {
            long long countA = 0;
            long long countB = 0;
            
            // sumA[i]와 같은 값의 개수를 모두 카운트
            while (i < sumA.size() && sumA[i] == a) {
                countA++;
                i++;
            }
            
            // sumB[j]와 같은 값의 개수를 모두 카운트
            while (j < sumB.size() && sumB[j] == b) {
                countB++;
                j++;
            }

            // 두 개수의 곱만큼 결과에 더하기 (쌍을 구하는 것 이므로 곱함)
            count += countA * countB;
        } else if (sum < T) {
            i++;
        } else {
            j++;
        }
    }

    cout << count;
    return 0;
}

이진 탐색

풀이 과정

1. A부분합과 B부분합을 구한다.
2. B부분합을 정렬한다.
3. t-A부분합을 저장한다.
4. t-A==B부분합이 되는 첫 지점과, 초과하는 부분을 찾는다(같은 부분합의 개수 구하기 위해)
5. count에 초과하는 부분 - 첫 지점을 한다.

구현

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

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int T, n, m;
    cin >> T >> n;
    
    int A[1000];
    for (int i = 0; i < n; i++) {
        cin >> A[i];
    }
    cin >> m;
    int B[1000];
    for (int i = 0; i < m; i++) {
        cin >> B[i];
    }
    
    // A의 모든 부분 배열의 합 계산
    vector<int> sumA;
    for (int i = 0; i < n; i++) {
        int current_sum = 0;
        for (int j = i; j < n; j++) {
            current_sum += A[j];
            sumA.push_back(current_sum);
        }
    }

    // B의 모든 부분 배열의 합 계산
    vector<int> sumB;
    for (int i = 0; i < m; i++) {
        int current_sum = 0;
        for (int j = i; j < m; j++) {
            current_sum += B[j];
            sumB.push_back(current_sum);
        }
    }

    long long count = 0;   
    sort(sumB.begin(), sumB.end());
    for(auto& a : sumA){
        int tmp = T-a;
        auto l = lower_bound(sumB.begin(), sumB.end(), tmp);//tmp와 같은 첫 값
        auto r = upper_bound(sumB.begin(), sumB.end(), tmp);//tmp 첫 초과값
        count += (r-l);
    }

    cout << count;
    return 0;
}

시간 복잡도

• 이진 탐색

$m^2$번 정렬($logm$)하므로 O($m^2 log m$)

sort(sumB.begin(), sumB.end());

sumA번($n^2$) sumB($m^2$)을 이진탐색 하므로 O($n^2 log{m}$ )

for(auto& a : sumA){
    int tmp = T-a;
    auto l = lower_bound(sumB.begin(), sumB.end(), tmp);
    auto r = upper_bound(sumB.begin(), sumB.end(), tmp);
    count += (r-l);
}

=> O($(n^2+m^2)log{m}$)

• 투 포인터

$n^2$번 정렬하고 $m^2$번 정렬 하므로 O($n^2 log n + m^2 log m$)

sort(sumA.begin(), sumA.end());
sort(sumB.begin(), sumB.end());

투 포인터의 경우

0~$n^2$까지, $m^2$~0까지 이므로 O($n^2+m^2$)이므로 영향 X

int i = 0, j = sumB.size() - 1;

while (i < sumA.size() && j >= 0) {
    int sum = sumA[i] + sumB[j];

    if (sum == T) {
        long long countA = 0, countB = 0;
        int a = sumA[i], b = sumB[j];
        
        while (i < sumA.size() && sumA[i] == a) {
            countA++;
            i++;
        }
        
        while (j >= 0 && sumB[j] == b) {
            countB++;
            j--;
        }

        count += countA * countB;
    } else if (sum < T) {
        i++;
    } else {
        j--;
    }
}

=>O($n^2 log n + m^2 log m$)