정수 배열 A가 주어졌을 때, 아래 조건을 모두 만족하는 인덱스 삼중항 (i, j, k)의 개수를 구하는 문제입니다.
0 <= i < 배열 A의 크기
0 <= j < 배열 A의 크기
0 <= k < 배열 A의 크기
또한 A[i] AND A[j] AND A[k]의 값이 0이 되어야 합니다. 여기서 AND는 비트 단위 AND(bitwise-AND) 연산자를 의미합니다.
문제 이해하기
예를 들어 입력이 [3, 1, 2]라면 출력은 12가 됩니다.
각 원소를 이진수로 표현하면 3 = 011, 1 = 001, 2 = 010입니다. 세 수의 비트 AND 연산 결과가 0이 되려면 세 수가 공통으로 1을 가지는 비트 자리가 하나도 없어야 합니다. 인덱스는 서로 달라야 하는 것이 아니라 범위 내에만 있으면 되므로, 같은 원소를 여러 번 선택하는 경우도 반드시 포함해야 한다는 점에 유의하세요.
접근 방법
세 개의 중첩 반복문으로 모든 조합을 확인하면 O(n³)의 시간이 걸립니다. 하지만 해시 맵(unordered_map)을 활용하면 O(n²)으로 최적화할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
먼저 두 원소의 비트 AND 결과(A[i] & A[j])가 나타나는 횟수를 해시 맵 m에 미리 계산해 저장합니다.
그다음 배열의 각 원소 x에 대해, 맵에 저장된 키와 x의 AND 연산 결과가 0이라면 해당 키의 등장 횟수만큼 정답에 더합니다. 이는 (A[i] & A[j]) & A[k] = 0을 만족하는 조합을 빠르게 집계하는 것과 같습니다.
알고리즘 단계
해시 맵 m을 하나 정의합니다.
ret := 0으로 초기화하고, n := 배열 A의 크기로 설정합니다.
i = 0부터 n-1까지, 그리고 j = 0부터 n-1까지 반복하면서 m[A[i] & A[j]]의 값을 1씩 증가시킵니다.
i = 0부터 n-1까지 반복하며 다음을 수행합니다.
x := A[i]
맵 m의 모든 키-값 쌍 a에 대해, (a.key AND x)가 0이면 ret := ret + a.value를 수행합니다.
최종적으로 ret을 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int countTriplets(vector<int>& A){
unordered_map<int, int> m;
int ret = 0;
int n = A.size();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
m[A[i] & A[j]]++;
}
}
for (int i = 0; i < n; i++) {
int x = A[i];
for (auto& a : m) {
if ((a.first & x) == 0) {
ret += a.second;
}
}
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {3,1,2};
cout << (ob.countTriplets(v));
}
입력
{3,1,2}
출력
12
복잡도 분석
첫 번째 단계에서 두 원소의 모든 쌍을 확인하므로 시간 복잡도는 O(n²)입니다. 공간 복잡도는 서로 다른 AND 결과의 가짓수에 비례하며, 최악의 경우 O(n²)입니다. 완전 탐색 방식의 O(n³)에 비해 훨씬 효율적인 접근법입니다.