[2024] day 152. leetcode 1442. Count Triplets That Can Form Two Arrays of Equal XOR
코딩테스트
2024년부터 새롭게 다시 시작하는 코딩테스트
2024년 5월 30일 (목)
Leetcode daily problem
1442. Count Triplets That Can Form Two Arrays of Equal XOR
Problem
정수 배열 arr이 주어지면
(0 <= i < j <= k < arr.length)인 세 개의 인덱스 i, j, k를 선택한다.
a와 b를 다음과 같이 정의할 수 있을 때
a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]
^는 비트별 XOR 연산을 나타낸다.
여기서 a == b 일 때, 부합하는 세 쌍의 개수(i, j, k)를 반환한다.
Solution
XOR operation (prefix XOR)
XOR 연산의 성질 이용해 해당 문제를 해결하는데,
여기서 필요한 성질 중 하나는 a^a=0 이고 a^0=a 이다.
즉, arr[i] ^ arr[i+1] ^ ... arr[k] = 0 이라면 특정한 j를 찾아 조건을 만족 시킬 수 있다.
배열의 부분 XOR 합인 prefix XOR을 계산한다.
prefix XOR을 계산하는 방법으로 Brute force 방법도 있고 two pass XOR 방식도 있지만 여기서는 one pass Prefix XOR로 접근해서, prefix XOR 계산과 결과 계산을 배열을 한 번만 탐색하면서 동시에 수행하는 것이다.
별도의 prefix XOR을 미리하는 계산 단계를 없애고, 현재 인덱스까지 XOR 값을 저장하는 변수를 두고, 배열을 순회하면서 각 요소와 XOR 값을 XOR 연산하여 해당 변수를 업데이트 한다. prefix ^= arr[i]
이렇게 하면 미리 계산된 prefix XOR 값이 현재 XOR 값과의 기여도를 실시간으로 계산 가능하다.
기여도를 계산하는 것은 이전 접근 방식과 동일하게, 미리 계산된 prefix XOR 배열 대신 실행중인 prefix 값을 사용한다.
참고로 XOR 연산의 주요 성질은
XOR 연산의 주요 성질
- 항등 성질 (Identity Property)
- 𝑎⊕0=𝑎
- 0과 어떤 수의 XOR 결과는 그 수 이다.
- 자기 자신과의 XOR (Self-Inverse Property):
- a⊕a=0
- 어떤 수와 자기 자신을 XOR하면 0이다.
- 교환 법칙 (Commutative Property):
- a⊕b=b⊕a
- 두 수를 XOR하는 순서는 중요하지 않다.
- 결합 법칙 (Associative Property):
- (a⊕b)⊕c=a⊕(b⊕c)
- XOR 연산은 결합 법칙을 따른다.
이 문제에서 중요한 성질은 연속된 구간의 XOR 결과가 0이 되는 조건이다.
문제의 조건은 두 구간
arr[i]⊕arr[i+1]⊕…⊕arr[j−1]와 arr[j]⊕arr[j+1]⊕…⊕arr[k]가 같다는 것으로 아래와 같이 변환할 수 있다.
arr[i]⊕arr[i+1]⊕…⊕arr[j−1]=arr[j]⊕arr[j+1]⊕…⊕arr[k]
위 식은 두 구간의 XOR가 같다는 것을 의미하고, (arr[i]⊕arr[i+1]⊕…⊕arr[j−1])⊕(arr[j]⊕arr[j+1]⊕…⊕arr[k])=0 로 변환 가능하다.
이를 다시 합치면 전체 구간의 XOR이 0이 되는 조건을 만족하게 된다.
arr[i]⊕arr[i+1]⊕…⊕arr[k]=0
즉, i부터 k까지 모든 요소의 XOR 결과가 0이 되면 i와 k 사이에 있는 j에 대한 Triplelet을 형성할 수 있다.
Code
class Solution:
def countTriplets(self, arr: List[int]) -> int:
n = len(arr)
cnt, prefix = 0,0
cnt_map = defaultdict(int)
total_map = defaultdict(int)
cnt_map[0] = 1
for i in range(n):
prefix ^= arr[i]
cnt += cnt_map[prefix] * i - total_map[prefix]
total_map[prefix] += i+1
cnt_map[prefix] +=1
return cnt- 유효한 Triplelet의 개수를 저장하기 위해 count를 0으로 초기화, 실행중인 XOR 값을 저장하기 위해 prefix를 0을 ㅗ초기화함
- 각 XOR 값의 발생 횟수를 저장하기 위해 countMap을 {0:1} 로 초기화
- 각 XOR 값이 발생한 인덱스의 합을 젖아하기 위해 'totalMap'을 빈 맵으로 초기화
- 배열 arr 를 순회하면서
현재 실행중인 XOR 값인 prefix를 arr[i]와 XOR 하여 업데이트한다.
현재 XOR값(prefix) 기여도를 countMap[prefix]와 totalMap[prefix]을 사용해서 계산한다.
계산된 기여도를 count에 더한다
현재 XOR 값의 발생 횟수를 업데이트하여 countMap[prefix]를 증가시킨다.
현재 XOR 값이 발생한 인덱스의 합을 업데이트하여 totalMap[prefix] 에 i+1을 더한다. - 유효한 Triplelet의 최종 개수를 반환한다.
Complexicity
시간 복잡도
배열을 한번만 순회하고 arr에서는 고정된 시간 O(1)에 수행되는 작업을 진행하므로 시간복잡도는 O(n) 이다.
공간 복잡도
추가 데이터 구조인 count_map, total_map에 의해 결정되므로, 해당 딕셔너리는 저장되는 키의 수에 비례해 공간 복잡도가 증가한다.
최악의 경우 두 딕셔너리가 배열의 모든 원소를 가질 수 있으므로 공간 복잡도는 O(n) 이다.
