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

 

 투포인터나 자료구조를 이용해서 푸는 문제. 배열의 크기 n은 최대 4,000으로 브루트 포스로는 절대 풀 수 없다. 로직 자체는 금방 떠올랐는데, 최적화 문제로 시간을 많이 썼다. 

 

 로직은 두 가지를 적용해 볼 수 있다. 먼저 투 포인터를 이용하는 방법이다. A, B, C, D 배열을 두 쌍으로 나누어 각각의 값을 교차시켜 더했을 때 나오는 결괏값 배열을 생성한다(O(n^2)). 그리고 생성된 두 합 배열을 정렬한다(O(n log n)). 이후엔 투 포인터를 이용해 하나의 배열은 시작점, 하나의 배열은 끝점부터 탐색하며 0이 되는 값을 찾아 나간다.(O(n^2)) 이때, 종료조건은 둘 중 한 배열을 가리키는 포인터가 반대쪽 끝에 도달했을 때로 설정해 두고, 더해서 0이 되는 모든 경우를 끝까지 탐색할 수 있도록 한다.

 물론 이 과정에서 투 포인터를 굳이 사용하지 않아도 된다, 두 합 배열을 생성해둔 상태에서 하나만 정렬하고 다른 정렬되지 않은 합 배열 값들에 대해 탐색을 시작한다. 탐색을 하면서 해당 값의 역수에 해당하는 값을 정렬된 합 배열에서 찾는다. 정렬이 되어 있으므로 이진탐색을 이용하면 upper bound와 lower bound를 쉽게 찾을 수 있고, 찾아낸 bound값들을 이용해 0이 되는 경우 값에 더해나가면 된다.

 

 나는 위의 방법이 아닌 map을 이용하는 방법을 사용했다. A, B, C, D배열의 두 쌍으로 나누는 것은 동일하다. 하지만 이번엔 map을 이용한다. 각 쌍 내의 합 조합을 map을 통해 저장하면(O(n log n)), 결과적으로는 배열이나 리스트를 사용할 때보다 원소 수가 줄게 된다. 나는 처음에 C++의 map 자체가 key값을 기준으로 정렬을 보장하므로, 이렇게 만들어진 두 map을 이용해 투 포인터로 탐색하는 방법을 썼다(O(n^2)). 그런데 이게 시간초과가 떠서 조금 아리송했다. 시간 복잡도를 러프하게 계산했을 때 시간 초과가 되지 않아야 하니까.

 

 C++의 map이나 set은 동작이 많이 느린 편이라, 기대 이하의 퍼포먼스를 보여줄 때가 많았던 것이 떠올라서 그냥 투 포인터가 아닌 map 자체의 인덱싱으로 탐색하기로 생각을 바꾸었다. 따라서 키 값을 기준으로 map이 정렬되어 있을 필요가 없으므로 C++ 내의 unordered_map을 이용하기로 했다. unordered_map은 해쉬 테이블을 기반으로 동작하기 때문에 삽입 과정에서 일반적으로 O(1)이 소모된다. 그리고 특정 key 값을 조회할 때도 일반적으로 O(1)이 소모된다. 그러므로 두 unordered_map을 만들어두고, 한쪽을 탐색하며 탐색 key값의 역수를 다른 한쪽의 unordered_map의 key값으로 넣어 찾아(O(n^2)) 두 value값을 곱해 0이 되는 경우 값에 더해준다. 

 그러나 이번에는 메모리 초과가 떴다. 메모리 제한은 1024 MB인데, 예상하기로는 이에 미치지 않을 것이라고 생각했다. <int, int> 쌍을 저장하는 해쉬 테이블이고, 일단 key-value 값들이 차지하는 메모리가 4,000*4,000(합 경우의 수)*8 bytes(두 개의 int) = 128MB 가량. 해쉬 테이틀에서 버킷 수가 요소 수의 2배 정도 생성된다고 생각하고, 각 버킷이 가지는 오버헤드를 대략 8바이트로 잡으면 4,000*4,000*2*8bytes = 256MB 가량. 둘을 합해도 400MB가 되지 않고 이런 unordered_map이 두 개가 생성되므로 800MB 정도에, 배열 A, B, C, D이 4*4,000*4bytes로 64KB니까 무시할 수 있는 수준이었다.

 아무래도 내 예상보다 버킷 수가 많아졌거나, 오버헤드가 차지하는 메모리가 크겠거니 싶어서 그냥 unordered_map을 하나만 생성하기로 했다. 왜냐면 배열 A, B에 대해서만 합을 unordered_map으로 만들어 놓고, 이후 C, D는 각각의 원소를 더해서 합을 찾아내면서 바로바로 unordered_map에서 합의 역수를 찾아보면 되니까.

 그렇게 코드를 변경하고 나서야 메모리 초과도 나지 않고 정상적으로 통과할 수 있었다. 처음부터 vector와 투 포인터 혹은 upper_bound, lower_bound 탐색을 이용하는 방법을 택했으면, 좀 더 빨리 해결했으려나 싶다.

 

#include <iostream>
#include <unordered_map>

using namespace std;

int a[4000];
int b[4000];
int c[4000];
int d[4000];

unordered_map<int, int> sumMap;

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n;
    scanf("%d", &n);

    for(int i=0; i<n; i++) {
        scanf("%d %d %d %d", &a[i], &b[i], &c[i], &d[i]);
    }

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            int sum = a[i]+b[j];
            sumMap[sum]++;
        }
    }

    long long result = 0;

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            int sum = c[i]+d[j];
            if(sumMap.count(-sum)==1) {
                result += sumMap[-sum];
            }
        }
    }

    printf("%lld", result);
}