BOJ 7453

22 May 2020 • ProblemSolving

합이 0인 네 정수

문제출처

문제 해석

정수로 이루어진 크기가 같은 배열 A,B,C,D가 있을 때, A[a]+B[b]+C[c]+D[d] = 0인 (a,b,c,d)쌍의 개수를 구하는 문제입니다.

설계(X)

배열 4개의 조합을 모두 탐색하는 방법은 O(N4)로 시간초과가 날 것입니다.

여기서 두개의 배열로 합치는 아이디어가 필요합니다.

배열 2개씩 묶어서 한개의 배열로 합칩니다 O(N2)

그리고, 그 배열들을 오름차순으로 정렬합니다. O(N2logN2)

그 후, 두개의 배열을 투포인터 알고리즘을 이용하여 가능한 쌍의 개수를 카운트합니다. O(N2)

여기서 주의할 점은 같은 수가 있는 경우, 첫번째 배열의 같은 수와 두번째배열의 같은수를 각각 카운트하여 곱을 취해주는 과정이 필요합니다.

이유는 가능한 모든 쌍의 개수를 구해야하기 때문입니다.

시간복잡도는 O(N2logN2)으로 시간안에 구현이 가능해 보입니다.

다른분들의 공개코드를 보면 거의 해쉬로 구현한 것을 볼 수 있습니다.

투포인터의 경우 시간복잡도는 O(N2)이지만 사실상 계산은 2xN2번 해야하기 때문에 N2이 커지면 그만큼 시간이 오래걸립니다.

그러나 해쉬를 사용하면 N2번 계산을 함으로써 (해쉬 추가하는 부분의 계산이 더 필요하겠지만 O(N2)보다는 적게 나올 것입니다) 더 빠른 시간안에 구현을 할 수 있습니다.

다른 풀이로는 이분탐색을 이용하는 방법인데 이를 이용할 경우 O(N2logN2)에 구현이 가능합니다.

이분탐색도 마찬가지로 실제 계산량을 보면 이분탐색을 두번 사용해야하므로 2xlogNxN2번의 계산이 필요합니다. 따라서 투포인터 알고리즘으로 구현한 것과 시간이 비슷하게 나올 것 같습니다.

구현(X)

코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 4000;
typedef long long ll;
int arr[4][MAXN+1];

vector<int> A, B;
int N;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[0][i] >> arr[1][i] >> arr[2][i] >> arr[3][i];
    }
    A.resize(N * N, 0);
    B.resize(N * N, 0);
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            A[i*N+j] = arr[0][i] + arr[1][j];
            B[i*N+j] = arr[2][i] + arr[3][j];
        }
    }
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    ll ans = 0;
    int low = 0;
    int high = N * N - 1;
    while (low < N * N && high >= 0) {
        if (-A[low] == B[high]) {
            int a_cnt = 0;
            int b_cnt = 0;
            int tmp = B[high];
            while (-A[low] == tmp && low < N * N) {
                a_cnt++;
                low++;
            }
            while (B[high] == tmp && high >= 0) {
                b_cnt++;
                high--;
            }
            ans += (ll)a_cnt * b_cnt;
        }
        else if (-A[low] > B[high]) {
            low++;
        }
        else high--;
    }
    cout << ans << "\n";
    return 0;
}
디버깅

벡터에 저장할 자료형을 long long으로 하는 실수를 하였습니다.

이 자료형을 사용할 경우 메모리 제한을 넘어서게 됩니다.

제출결과

메모리: 127056KB, 시간 : 984 ms

마무리

투포인터를 활용한 문제였습니다.

배열을 두개로 합치는 아이디어가 필요한 문제로, 다양한 알고리즘으로 해결이 가능합니다.

그러나, 문제 자체가 알고리즘을 풀이하는게 아닌 최적화 또한 고려해야하는 문제로 백준 사이트에서 풀이할 만한 문제는 아닌 것 같습니다.

예로, c++의 경우 unordered_map 함수를 사용하면 시간초과가 난다고 합니다.(해쉬를 별도로 커스터마이징해야합니다)

 BOJ

Related Posts