1442_java.md

1442. Count Triplets That Can Form Two Arrays of Equal XOR

Summary

🙇‍♂️ URL : https://leetcode.com/problems/count-triplets-that-can-form-two-arrays-of-equal-xor/
🤷‍♂️ Difficulty: Medium
💆‍♂️ Submissions

• RunTime: 38 ms, faster than 10.20% of Java online submissions
• Memory Usage: 39 MB, less than 6.27% of Java online submissions

Source code

class Solution {
    public int countTriplets(int[] arr) {
        int result = 0;
        int[][] ijmap = new int[arr.length][arr.length];
        int[][] jkmap = new int[arr.length][arr.length];

        if(arr.length == 2) {
            if (arr[0] == arr[1]) {
                return 1;
            } else {
                return 0;
            }
        }

          // 인덱스 i, j의 모든 경우에 대한 XOR 결과 저장
        for(int i=0; i<arr.length-1; i++) {
            for(int j=i+1; j<arr.length; j++) {
                if((j-1)>i) {
                    ijmap[i][j] = ijmap[i][j-1]^arr[j];    
                } else {
                    ijmap[i][j] = arr[i]^arr[j];
                }
            }
        }

        // 인덱스 j, k의 모든 경우에 대한 XOR 결과 저장        
        for(int j=1; j<arr.length; j++) {
            for(int k=j; k<arr.length; k++) {
                if(j==k) {
                    jkmap[j][k] = arr[j]^arr[k];    
                } else {
                    jkmap[j][k] = jkmap[j][k-1]^arr[k];
                }
            }
        }

        //0 <= i < j <= k < arr.length
        for(int i=0; i<arr.length-1; i++) {
            for(int j=i+1; j<arr.length; j++) {
                for(int k=j; k<arr.length; k++) {
                    if(ijmap[i][j] == jkmap[j][k]) {
                        result++;
                    }    
                }  
            }
        }
        return result;
    }
}

How to Approach

인덱스 i,j,k가 각각 0 <= i < j <= k < arr.length의 범위를 가진다고 할 때,

• a = arr[i] ^ arr[i + 1] ^ ... ^ arr[j - 1]
• b = arr[j] ^ arr[j + 1] ^ ... ^ arr[k]

를 만족하는 a == b의 갯수를 구하는 문제이다.

이 문제는 인덱스(i, j)에 대한 XOR 결과를 저장하는 2차원 배열 ijmap과, 인덱스(j, k)에 대한 XOR 결과를 저장하는 jkmap 각각을 만들어서 (i, j)까지의 XOR값과 (j, k)까지의 XOR 값의 일치 여부를 확인해주었다. DP라고 하기엔 애매하지만, 2차원 행렬을 사용한다는 유사한 방식을 이용해서 해결하였고 생각보다 쉽게 해결할 수 있었다.