[Hash-table, Bitset] boj 7453 합이 0인 네 정수

evelyn82ny·2022년 2월 12일
0

Algorithm

목록 보기
2/9

문제 링크: https://www.acmicpc.net/problem/7453
전체 코드: https://github.com/evelyn82ny/Algorithm/blob/master/Graph/ps/boj_7453.cpp

배열 A, B, C, D 에서 각 1개씩 골라 4개의 합이 0 이 되는 경우의 수를 구하는 문제이다. 배열의 최대 크기는 4,000 이고 배열에 들어있는 정수의 절대값은 최대 2^28 이다.

4개의 배열에서 brute force 를 적용하면 O(N^4) = O(4,000^4) 의 시간복잡도를 갖기때문에 해당 방법으로 문제를 해결할 수 없다.

Meet in the middle 을 적용해 O(N^2) + O(N^2) 으로 분리하면 O(2 * (N^2)) = O(N^2) = O(16,000,000) 의 시간복잡도이므로 시간내에 해결할 수 있다. 배열 A 와 B 에서 구한 합 X 와 배열 C 와 D 에서 구한 합 -X 가 존재하면 4 개의 정수의 합이 0 이 되기 때문에 meet in the middle 을 적용해 해당 문제를 해결할 수 있다.

위 방식으로 구현하기 위해 2개의 배열을 먼저 더한다음 자료구조에 넣어준다. 2개의 배열을 더한 결과가 중복될 수 있다. 만약 배열 A와 B에서 구한 합을 vector에 저장했다고 하자. 배열 C 와 D 에서 구한 합 X 에 대하여 배열 A 와 B 에서 구한 합들 중 -X 을 모두 찾아야 한다. vector 를 정렬한 다음 upper_bound 를 사용해 개수를 구할 수 있다.

또 다른 방법으로는 map 에 배열 A와 B에서 구한 합을 key 로, value 를 개수로 지정한다. 배열 C 와 D 에서 구한 합 X 에 대하여 map 에서 key 가 -X 인 value 가 X 와 조합하여 0을 만들 수 있는 경우의 수가 된다.

unordered_map

출처 : wikipedia

map 은 Red-Black Tree 기반이므로 Key 순서를 유지하기 때문에 탐색에 있어 O(logN) 의 시간복잡도를 갖는다. 반면 unordered_map 은 hash-table 을 사용하기 때문에 key 의 순서를 유지하지 않아 탐색에 있어 O(1) 의 시간복잡도를 갖기 때문에 조금 더 빠른 속도를 보여준다.

시간: 11,580 ms, 메모리 694,292 KB

unordered_map<int, int> sumCount;
for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            sumCount[a[i] + b[j]]++;
    
long long answer = 0;
for(int i = 0; i < n; ++i) {
	for(int j = 0; j < n; ++j) {
    	auto iter = sumCount.find(-(c[i] + d[j]));
        if(iter != sumCount.end())
        	answer += iter -> second;
    }
}

bitset

unordered_map 을 사용하는 이유는 찾고자하는 값이 몇개가 존재하는지 구하기 위함이므로 vector<bool> 와 같이 방문처리를 적용해 애초에 존재하지 않는 값에 대해서 map 에서의 탐색을 막으면 시간을 줄일 수 있지 않을까라는 생각이 들었다.

값의 존재 유무를 vector<bool> 로 표현해도 되지만, 메모리를 조금이라도 줄이기 위해 bitset 을 적용했다. bool Type 은 2 Byte 이므로 1개의 존재 유무를 표현하고자 2 Byte 가 필요하다. 하지만 bitset 은 1개의 존재 유무를 표현하기 위해 1 bit 만 사용되므로 표현하고 싶은 수가 많은 수록 bitset 을 사용하는 것이 유리하다고 생각한다.

시간: 10,492 ms, 메모리: 825,428 KB

bitset<(1 << 30) + 1> isExist;
unordered_map<int, int> sumCount;

void add(int num) {
    if(!isExist[num + BASE])
        isExist[num + BASE] = true;
    sumCount[num]++;
}

int getCount(int num) {
    if(!isExist[num + BASE])
        return 0;
    return sumCount.find(num) -> second;
}

bitset 을 적용해 getCount method 에서 값을 찾을 때 이미 존재하는 값에 대해서만 map 에 접근할 수 있도록 구현했지만 시간을 많이 줄이지 못했다. 이는 unordered_map 은 hash-table 기반이므로 key 를 찾는데 O(1) 의 시간복잡도를 갖기 때문에 bitset 의 기능을 제대로 살리지 못했기 때문이다.

그래서 이번엔 값을 추가하는 함수에서도 map 에 접근을 줄일 수 있는 방법을 적용했다.

시간: 1,920 ms, 메모리: 242,188 KB

결론적으로 값을 추가하는 add method 에도 unordered_map 에 접근하는 경우를 줄여보니 시간이 많이 줄어든 것을 확인할 수 있었다.

bitset<(1 << 30) + 1> isExist;
unordered_map<int, int> sumCount;

void add(int num) {
    if(!isExist[num + BASE])
        isExist[num + BASE] = true;
    else
        sumCount[num]++;
}

int getCount(int num) {
    if(!isExist[num + BASE])
        return 0;
    auto iter = sumCount.find(num);
    return iter == sumCount.end() ? 1 : iter -> second + 1;
}

기존 코드에 bitset 을 적용한 이유는 애초에 존재하지 않는 수에 대해서는 unordered_map 에서의 탐색을 막기 위함이였다. 즉, 찾고자 하는 수에 대해 bitset 이 true 값을 가지고 있다면 이는 해당 수가 1개 이상 존재한다는 의미이다.

2개의 배열을 더한 합을 add method 를 통해 저장할 때 isExist 가 false 이면 해당 수는 처음 저장되는 수임을 뜻한다. 즉, 이때 isExist 만 true 로 설정하고 map 에는 저장하지 않아 접근을 막는다. 만약 isExist 가 true 반환하면 해당 수는 이전에도 만들어진 수이므로 unordered_map 에 접근해 value 값을 증감한다.

그리고 getCount method 에서 값을 찾을 때 isExist 가 true 이면서 sumCount 에서 해당 수를 찾았을 때 unordered_map 의 end() 을 반환한다면 해당 수를 Key 로 존재하지 않기 때문에 해당 수가 1개만 존재한다는 뜻이다. getCount method 가 조금 복잡해졌는데 isExist 가 true 이면 몇 개가 존재하는지 알기위해 무조건 unordered_map 에 접근해야 하기 때문에 getCount method 의 성능은 이전과 다름없다고 본다.

rehash

unorderd_map 은 hash-table 기반이므로 bucket 수를 조정해 시간을 조금 더 줄였다.

시간: 1,336 ms, 메모리: 359,548 KB

bitset<(1 << 30) + 1> isExist;
unordered_map<int, int> sumCount;

sumCount.rehash(1 << 24);

void add(int num) {
    if(!isExist[num + BASE])
        isExist[num + BASE] = true;
    else
        sumCount[num]++;
}

int getCount(int num) {
    if(!isExist[num + BASE])
        return 0;
    auto iter = sumCount.find(num);
    return iter == sumCount.end() ? 1 : iter -> second + 1;
}

unordered_map 의 rehash 함수로 1 << 24 이상의 bucket 수로 변경하고 hash-table 을 다시 build 한다. 1 << 24 로 설정했을때가 제일 빠른 속도였다.

Reference

profile
🌈 즐겨보자고 🙌🏻

0개의 댓글