문제 출처
비트연산자, 그 중에서도 XOR의 특성을 알면 쉽게 풀 수 있는 문제였다.
요즘 리트코드 데일리 문제를 하나씩 푸는 재미에 꽂혔다.
작년 이맘 때 즈음엔 비트연산자 문제가 나오면 스트레스를 받았는데,
요즘엔 오히려 비트연산자가 더 재미있다는 느낌을 받았다.
이 문제를 이해한 바로는 아래와 같다.
- 전체 배열에서 시작 인덱스 i, 끝 인덱스 j를 정한다.
- 그리고 그 끝 인덱스의 다음인 j+1에서, 또다른 끝 인덱스 k를 정한다.
- 이 때 i부터 j까지 XOR한 값과 j+1부터 k까지 XOR한 값이 같을 경우 그 경우를 센다.
- 그렇게 센 모든 경우의 수를 반환한다.
이걸 풀기 위한 접근은 XOR의 특성을 가지고 설명해야 한다.
XOR를 이용한 아이디어 구상하기
XOR 연산은 두 비트가 다르면 1, 같으면 0을 반환한다.
즉, 아래와 같은 기본 식이 성립된다.
x ^ x = 0, x ^ 0 = x
그렇다면 i~j까지를 a라고, j+1부터 k까지를 b라고 한다면, a ^ b는 어떻게 될까?
i~(j-1) = a, j~k = b일 때, a ^ b = 0이러한 식이 성립한다.
즉, 우리가 세어야 할 경우의 수는 다음과 같다.
i^(i+1)^...^k = 0인 i와 k를 구하고 그 속에서 j
여기까지 x ^ x = 0이라는 식 하나만을 가지고 만들 수 있는 아이디어였다.
이제 x ^ 0 = x를 같이 이용해 아이디어를 계속 해나갈 것이다.
i~k를 XOR한 값은 아까 말했듯이 0이어야 한다. from 부터 to 까지 XOR한 값을 XOR(from, to)라고 하겠다.
이전의 x ^ 0 = x라는 식과, x ^ x = 0이라는 두 식을 이용할 것이다.
XOR(from, to) = 0이런 식에서 양쪽에 from을 XOR해주자.
XOR(from, to) ^ from = 0 ^ from = from여기에서 왼 쪽에는 이미 from이 XOR연산으로 추가되어있다. 그렇기에 x ^ x = 0으로 소거된다.
그렇게 식은 다음과 같이 바뀐다.
XOR(from + 1 , to) = from그런데, 아무것도 없는 상태에서 from인덱스의 값만을 XOR해주어도 from이 나온다.
그 다음 경우를 생각해볼까?
XOR(from + 1 , to) ^ (from+1) = from ^ (from+1)
XOR(from + 2, to) = XOR(from, from+1)이렇게 계산할 수 있다. 이전의 소거와 추가를 생각하면 된다.
그렇기에 도달할 수 있는 결론이 생긴다.
j는 셀 필요 없다. XOR(i, j)에서 j의 범위만 구해주면 된다.
위의 조건에서 보면 i < j <= k라고 되어있다.
즉, i와 k의 범위를 안다면, k - i를 해주면 그게 해당 범위 내에 존재하는 Triplets이 된다.
코드로 만들기(JAVA)
i의 범위는 조건을 보았을 때, arr.length-1로 잡아주면 된다.
왜냐하면 조건상 k도 arr.length보다 작아야 하는데, i < k기 때문이다.
k는 i+1부터 arr.length보다 작은 동안 반복시켜주면 된다. 그 동안 하나씩 XOR해주면 된다.
i부터 하나씩 XOR할 때, XOR한 값이 0이면 그 때 마다 k - i를 구해 누적해주면 된다.
public int countTriplets(int[] arr) {
int count = 0;
for(int from = 0; from < arr.length-1; from++) {
int xorValue = arr[from];
for(int to = from+1; to < arr.length; to++) {
xorValue ^= arr[to];
if(xorValue == 0) {
count += to - from;
}
}
}
return count;
}그렇게 이런 답을 만들었다.
그럼...twenty thousand...🔥