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

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

7453번: 합이 0인 네 정수

처음에 풀 때는 정신없이 풀었는데 왜 굳이 이렇게 풀었는지 한 번 정리해볼 필요가 있어보였다.

효율성을 생각하지 않는다면 A,B,C,D 배열 요소마다 조합을 만들어서 배열의 합이 0인지를 확인한다. 이렇게 된다면 $O(N^4)$이라는 시간복잡도를 가지게 된다. (비효율 그자체..)

 

이런 상황을 방지하기 위해 A,B 배열을 합치고 C,D 배열을 합쳐서 4개의 배열을 2개의 배열로 만든다. 이로써 각각 $O(N^2)$라는 시간복잡도를 가지도록 한다. 그리고 A와 B를 합친 값과 C와 D를 합친 값의 합이 0이 되도록 하는 조합을 찾아야 한다. 그리고 후에 정렬로 $O(nlogn)$, 이분탐색 기반의 lower_bound, upper_bound을 사용하면서 이 부분에서는$O(logn)$이라는 시간 복잡도가 소요된다.

따라서 최종적으로 $O(n^2logn)$의 복잡도를 가지므로 4개의 배열을 모두 조합해보는 경우보다는 효율적이다.

 

💡깨알팁

미리 메모리 공간을 확보(할당)하고 인덱스로 값을 넣어주는 게 매번 push_back하는 것보다 빠르다.

equal_range는 lower_bound, upper_bound를 동시에 리턴한다.

 

왜 map을 쓰면 시간이 초과할까?

많은 사람들이 질문에 map을 사용한 후 시간이 초과한다는 질문을 남겨서 이에 대한 고민도 해소해보려고 한다.

사람들은 아무래도 A와 B를 합친 값과 C와 D를 합친 값을 key로, 등장하는 횟수는 value로 각각 map으로 만들어서 조합을 간편하게 만들려고 했던 것 같다. 하지만 이는 실패로 돌아가고 마는데,,,

왜냐하면 해시 충돌(Hash Collison)로 인해 map의 효율적인 알고리즘이 수포로 돌아가고 만다.

해시충돌로 인해 랜덤 접근이 불가능해지고 최악의 경우 $O(N)$의 시간 복잡도를 가지게 된다. 따라서 이분 탐색 기반의 lower_bound, upper_bound보다 비효율적인 탐색이 될 가능성이 생긴다.

 

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

using namespace std;

int main() {
    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];
    }
    
    vector<int> first, second;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < n;j++){
            first.push_back(a[i] + b[j]);
            second.push_back(c[i] + d[j]);
        }
    }
    
    sort(second.begin(), second.end());
    long long ans = 0;
    for(int num : first) {
        auto range = equal_range(second.begin(), second.end(), -num);
        ans += range.second - range.first;
    }
    cout << ans << endl;
    return 0;
}