Count Triplets That Can Form Two Arrays of Equal XOR

문제 번호, 이름: 1442. Count Triplets That Can Form Two Arrays of Equal XOR

문제 링크: https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/description

날짜: 2024/05/30

상태: 완료

 

이 문제를 고른 이유

리트코드 오늘의문제

문제 보고 처음 든 생각

xor은 다시 자기 자신을 xor 해주면 취소된다는게 문제의 핵심이긴 할텐데 어떻게 최적화를 할까

풀이 v1

• 소요 시간 20분

class Solution:
    def countTriplets(self, arr: List[int]) -> int:
        cumulative_xor = [arr[0]]
        for elem in arr[1:]:
            cumulative_xor.append(cumulative_xor[-1] ^ elem)
        
        arr_len = len(arr)

        answer = 0
        for i in range(0, arr_len - 1):
            for k in range(i + 1, arr_len):
                a = arr[i]
                b = cumulative_xor[k] ^ cumulative_xor[i]
                if a == b:
                    answer += (k - i)
        
        return answer

 

1. 일단 brute force 방식이 먹힐지 시간복잡도 계산을 해 보았다 arr length가 N이라고 했을 때

i, j, k 3중 loop를 돌아야 하니까 일단 O(N^3) 에다가 각 loop 안에서 xor 연산도 N번 해야 하니까 최종적으로 O(N^4). N<=300 이니까 아슬아슬하게 안 될 것 같다

그럼 O(N^3logN) 이나 O(N^3) 풀이만 찾아도 돌기는 할 것이다

 

2. i, k에 대해서만 loop를 돌면서 (O(N^2)) 우선 초기 연산으로 i부터 k까지의 element를 모두 xor해준 값을 들고 있고 (O(N)), j를 하나 키울 때마다(O(N)) xor을 앞쪽 집합에 한 번, 뒤쪽 집합에 한 번 (O(1)) 하는 방법을 생각해 냈다. 최종적으로는 O(N^3)

그런데 오늘의 감이 왠지 이것보다 더 좋은 풀이가 있을 거라고 했다

 

3. 메모리를 좀 더 쓸 수도 있겠지만, 우선 함수 초기에 arr의 앞에서부터 쌓아가면서 처음부터 본인까지의 xor한 값을 저장해 두기로 했다. 그래서 나중에 i부터 k까지의 xor한 값을 구하려면, cumulative_xor[k] ^ cumulative_xor[i-1] 로만 바로 구할 수 있도록 했다.

또 하나 중요한 사실은, i, k가 주어졌을 때 어떠한 j에 대해 a == b 라면 그 때에는 모든 j에 대해서 a == b를 만족한다. j를 iteration 할 필요가 없다

그래서 i, k loop를 돌면서(O(N^2)) 하나의 j에 대해서만 a == b가 같은지 체크 (cumulative_xor 덕분에 O(1))하도록 구현했다. 최종적으로 O(N^2) 이다.

 

 

다른 사람 풀이 중에 시간복잡도 O(N^2), 공간복잡도 O(1)인 풀이가 있었다. 내껀 공간복잡도는 O(N)이니까 한 수 배웠다.

i, k 가 주어졌을 때 a == b 라면, i부터 k까지를 전부 xor했을 때 0이 나온다는 사실을 이용했더라. 이러면 굳이 a와 b를 구해서 비교할 필요가 없으니 cumulative_xor를 유지할 필요가 없다 waaa!

풀이 v2

• 소요 시간 -

# v2 없음

 

 

이 문제를 풀고 얻은 것

• python의 xor이 ^ 였다는 기억 되새기기
• 다른 medium 단계 문제보다 시간은 더 걸렸지만, 퍼포먼스 통계를 봤더니 속도도 빠르고 메모리도 적게 쓴 풀이여서 얻은 짜릿함

메모

• 시간복잡도를 생각해가며 풀이해보는 연습을 했다