99클럽 코테 스터디 27일차 TIL Find The Original Array of Prefix Xor

https://leetcode.com/problems/find-the-original-array-of-prefix-xor/description/

 

 

 

1. 문제 및 접근

 

 

2433. Find The Original Array of Prefix Xor

비트연산 xor

pref[0] = arr[0]

pref[1] = arr[0] ^ arr[1]

arr[1] = arr[0] ^ pref[1]

pref[2]=  arr[0]^arr[1]^arr[2]

arr[2] =  arr[0]^arr[1]^pref[2]

 

 

 

 

 

XOR ?

 

 

 

 

 

2.  풀이

 

public int[] findArray(int[] pref) {


    int arr[] = new int[pref.length];
    arr[0] = pref[0];

    int answer = arr[0];
    int now = arr[0];


    for (int i = 1; i < pref.length; i++) {


        arr[i] = now ^ pref[i];
        now = now ^ arr[i];



    }
    return arr;

}

 

 

 

xor의 분배법칙을 이용하면 된다고 한다.

(문제 자체가 생소해서 찾아봄)

 

pref[]의 배열이 주어질 때,

 

pref[i] = arr[0]^arr[1]^arr[2]^arr[i]로 이루어져있고,

 

0~i까지 xor 연산된 값이라는 뜻

 

문제에서 요구하는 것은 xor연산되기 전의 arr를 구하면 됨

 

 

 

 

 

 

 

 

2-1.  식 세우기

 

pref[0]  = arr[0]

pref[1]  = arr[0] ^ arr[1]

arr[1]    = arr[0] ^ pref[1]

pref[2] =  arr[0]^arr[1]^arr[2]

arr[2]   =  arr[0]^arr[1]^pref[2]

 

 

 

 

 

 

 

arr[]의 배열은 누적합을 구하기 위함

 

 

pref[0]의 값은 arr[0]이고,

 

 

현재 누적합의 수를 now로 지정

 

 

 

 

 

 

 

 

 

2-2. arr[i]값 구하기

 

 

 

arr[i]는

 

분배법칙에 의해

 

{ pref[1]  = arr[0] ^ arr[1] }    =    {arr[1]    = arr[0] ^ pref[1]}

 

즉 이때까지 더해진 arr[i] 값들과 현재 pref[i] 의 ^ 연산의 값이다.

 

 

그리고 now에 다시 현재 arr[i]을 누적 시켜준다.

 

 

 

 

 

 

 

 

 

 

 

성공!

 

 

 

 

 

3.  마무리

 

 

^연산과 분배법칙을 보고, 쉽게 풀어낼 수 있었는데,

 

now 값을 잘못 계산해서 누적합으로 시작해줘야 하는데 0으로 초기화해서 시작한 작은 이슈가 있었다.

 

쉬운 수학문제라 차근히 식을 세워 나가면서 쉽게 접근할 수 있었다.

 

문제가 쉬워서 더 풀어봐야하지만,, 오늘은 주말이다 하루만..