LeetCode / Array / 1442번 / Count Triplets That Can Form Two Arrays of Equal XOR / JS

< 문제 바로가기 >

 

< 문제 간단설명 >

정수로 이루어진 배열 arr가 주어진다.

3개의 index가 주어지는데, 각각 i, j, k라고 하자. 이들은 다음과 같은 상관관계를 갖는다.

• 0 <= i < j <= k < arr.length

그리고 우리는 이것을 이용해서 a와 b를 찾아야한다. a와 b는 다음과 같다.

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

여기서 ^는 bitwise-xor 이다.

 

a와 b가 같게되는 i, j, k쌍의 개수가 몇개인지 반환하면 되는 문제이다.

 

< 제약 조건 >

• 1 <= arr.length <= 300
• 1 <= arr[i] <= 100,000,000

 

1. 실패 코드 - 시간 초과

/**
 * @param {number[]} arr
 * @return {number}
 */
var countTriplets = function(arr) {
    const len = arr.length;
    let count = 0;
    
    // O(n)
    const getTotalXor = (start, end) => {
        let result = 0;
        for(let i=start; i<=end; i++) {
            result ^= arr[i];
        }

        return result;
    }

    // O(n)
    for(let i=0; i<len; i++) {
    	// O(n)
        for(let j=i+1; j<len; j++) {
            // O(n)
            for(let k=j; k<len; k++) {
                const a = getTotalXor(i, j-1);
                const b = getTotalXor(j, k);

                if(a === b) {
                    count++;
                }
            }
        }
    }

    return count;
};

 

아무래도 반복문이 많다보니, O(n^4)의 시간복잡도를 가지기 때문에 시간초과가 날 수 밖에 없다.

 

 

2. 성공 코드

/**
 * @param {number[]} arr
 * @return {number}
 */
const countTriplets = (arr) => {
  const len = arr.length;
  const prefix = Array.from({ length: len + 1 }, () => 0);

  // prefix[i + 1] = arr[0] ^ ... ^ arr[i]
  for (let i = 0; i < len; i++) {
    prefix[i + 1] = prefix[i] ^ arr[i];
  }

  let count = 0;
  for (let i = 0; i < len; i++) {
    for (let k = i + 1; k < len; k++) {
      /*
      만약 i-1까지의 XOR 결과와 k까지의 XOR 결과가 같다면,
      그 사이에 존재하는 j는 모두 답이된다.

      arr[0] ^ ... ^ arr[i-1] = arr[0] ^ ... ^ arr[k]

      같은 부분을 제거하면 다음과 같이 된다.
      arr[i] ^ ... ^ arr[k] = 0 (*)

      j를 사용하면 다음과 같이 나타낼 수 있다.
      arr[i] ^ arr[i+1] ^ ... ^ arr[j-1] = arr[j] ^ arr[j+1] ^ ... ^ arr[k]

      약간의 설명을 덧붙이자면, XOR은 비교하는 두 값이 같으면 0이 된다.
      따라서 0 ~ j-1까지 XOR을 한 것과,
      j ~ k까지 XOR을 한 것이 같다면,
      둘이 XOR을 할 경우 0이된다.
      이것은 결국 붙여쓰면 위의 (*) 라인과 같이 된다.
      */

      // i초과, k이하인 j의 개수를 센다.
      if (prefix[i] === prefix[k + 1]) {
        count += k - i;
      }
    }
  }

  return count;
};