level - hard
[문제 내용]
nums 배열에서 nums[i] & nums[j] & nums[k] == 0 인 i, j, k를 찾아 총 개수 반환
[example 1]
Input: nums = [2,1,3]
Output: 12
Explanation: We could choose the following i, j, k triples:
(i=0, j=0, k=1) : 2 & 2 & 1
(i=0, j=1, k=0) : 2 & 1 & 2
(i=0, j=1, k=1) : 2 & 1 & 1
(i=0, j=1, k=2) : 2 & 1 & 3
(i=0, j=2, k=1) : 2 & 3 & 1
(i=1, j=0, k=0) : 1 & 2 & 2
(i=1, j=0, k=1) : 1 & 2 & 1
(i=1, j=0, k=2) : 1 & 2 & 3
(i=1, j=1, k=0) : 1 & 1 & 2
(i=1, j=2, k=0) : 1 & 3 & 2
(i=2, j=0, k=1) : 3 & 2 & 1
(i=2, j=1, k=0) : 3 & 1 & 2[해결 방법]
아직도 뇌가 조합알고리즘에 미쳐있어서 잠깐 좀 헤맸다..
간단한 해결방법으로는
i와 j를 먼저 모두 계산하여 그 결과값들의 count를 저장하고
나머지 k를 다시 그 저장한 계산한값과 연산하여 0이 되는 값을 찾아서
그 모든 count들을 다 더했다.
class Solution {
public int countTriplets(int[] nums) {
int n = nums.length;
HashMap<Integer, Integer> nMap = new HashMap<>();
for (int num : nums) {
for (int i : nums) {
int result = num & i;
nMap.put(result, nMap.getOrDefault(result, 0) + 1);
}
}
int result = 0;
for(int num : nums) {
for(int key : nMap.keySet()) {
if((num & key) == 0) {
result += nMap.get(key);
}
}
}
return result;
}
}