[Python/코테] LeetCode 2433. Find The Original Array of Prefix Xor

2433. Find The Original Array of Prefix Xor

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

* 대충 번역: 크기가 n인 정수 배열 pref가 주어진다. pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i] 을 만족하는 크기가 n인 배열 arr을 찾아 반환하라. ^는 비트 XOR 연산자이다.

알고리즘 설계

💡idea.

문제 조건을 수식으로 만들면 다음과 같다.

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

arr[0] = pref[0] 이므로, 아래 두 식이 같다. 

pref[1] = pref[0] ^ arr[1] 
# 즉,
arr[1] = pref[0] ^ pref[1]

 

따라서, 다음과 같은 수식도 성립한다.

pref[2] = pref[1] ^ arr[2]
# 즉,
arr[2] = pref[1] ^ pref[2]

결국 아래와 같은 식이 성립하게 된다.

arr[i] = pref[i] ^ pref[i-1] # 0 < i

 

🎲step.

초기값 arr[0] = pref[0] 을 지정해주고, 찾은 식을 대입하여 arr 값들을 계산해낸.

알고리즘 구현

class Solution(object):
    def findArray(self, pref):
        """
        :type pref: List[int]
        :rtype: List[int]
        """

        n = len(pref)

        arr = [0]
        arr[0] = pref[0]

        for i in range(1, n):
            # arr[i] = pref[i] ^ pref[i-1]
            arr.append(pref[i] ^ pref[i-1])

        return arr

나다어

나는 다음에 어떻게 풀까

비트 연산자는 다음과 같은 설명을 만족한다. (출처: https://wikidocs.net/20704)

• 비트 단위로 연산을 수행합니다.
• 0은 거짓으로 1은 참으로 연산하여 결과를 1과 0으로 반환합니다.
• "^(xor)"연산은 두개의 값이 다를 때만 참인 연산입니다.