[코테연습] 1310. XOR Queries of a Subarray

- 비트문제 / dp 문제

 

https://leetcode.com/problems/xor-queries-of-a-subarray/submissions/1388253676/?envType=daily-question&envId=2024-09-13

 

- 문제분석

1. int[] arr 매개변수와 int[][] queries 매개변수가 있다.

2. arr 에는 계산해야하는 숫자이며, queries 는 arr[queries[0]] ~ arr[queries[1]] 로 arr 의 몇번째 배열부터 계산할지에 대한 쿼리를 말한다.

3. 계산은 비트 XOR 로 계산하며 arr[x] ~ arr[y] 의 모든 XOR 값을 구한다.

 

 

- 문제풀이

1. 단순히 2중 for 문으로 해결할 수 있지만, dp 의 prefix 개념을 이용하여 시간복잡도 O(N) 으로 구해보자.

2. 먼저 int[] dp = new int[arr.length] 를 선언한다.

2-1. dp[0] = arr[0] / dp[1] = dp[0] ^ arr[1] / dp[2] = dp[1] ^ arr[2] 로 반복하여 dp[i+1] 의 값을 0 ~ i 까지의 XOR 을 계산한 값으로 초기화한다.

3. 그 이후 queries 를 반복문으로 반복하면서, left가 0일때는 0~ right 로 취급되므로 dp[right] 를 리턴한다.

4. left 가 1이상일 때는, dp[right] - dp[left] 를 하기 위해서 dp[right] ^ dp[left-1] 을 리턴한다.

 

 

class Solution {
    public int[] xorQueries(int[] arr, int[][] queries) {
        int[] result = new int[queries.length];
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        //dp[1] = dp[0] ^ arr[1];
        //dp[2] = dp[1] ^ arr[2];
        //dp[3] = dp[2] ^ arr[3];
        for(int i = 1; i < arr.length; i++) {
            dp[i] = dp[i-1] ^ arr[i];
        }
        int idx = 0;
        for (int[] q : queries) {
            int left = q[0];
            int right = q[1];

            if (left == 0) {
                //arr[0] ~ arr[right] 를 수행한 값 
                result[idx++] = dp[right];
            } else {
                //dp[right] = arr[right] ~ arr[0] 을 수행한 값이므로,
                //arr[right] ~ arr[left] 를 구하기 위해서는 dp[right] - dp[left-1] 값과 같다. 
                result[idx++] = dp[right] ^ dp[left-1];
            }
        }
      
        return result;
    }
}