[99클럽 코테스터디 2기] [미들러 문제] Find The Original Array of Prefix Xor

[Find The Original Array of Prefix Xor]

문제

입력과 출력

코드

class Solution:
    def findArray(self, pref: List[int]) -> List[int]:
        arr=[0 for i in range(len(pref))]
        arr[0]=pref[0]

        val=pref[0]

        for i in range(1,len(pref)):
            arr[i]=val^pref[i]
            val^=arr[i]

        return arr

알고리즘

먼저 arr 요소를 바로바로 대입해주기 위해
0으로 pref 길이만큼 arr 배열을 초기화해준다.
첫번째 요소는 연산할 것이 없으니까 바로 대입해주고,
누적하여 연산을 할 수 있게 val값에 첫번째 요소를 담아준다.
for문을 통해 val에는 누적 연산값을, arr의 i번째 요소에는 누적연산값과 현재 값을 연산하여 넣어준다.

회고

처음에는 이렇게 구현했었다.
그러나 이런 식으로는 타입이 맞지 않는 것 같았고, 검색을 통해 조금 수정할 수 있었다.
처음 코드가 틀리진 않았지만 알고리즘에서 크게 벗어나지는 않아서 다행이였다.

누적값을 어떻게 받아야할지가 고민이였는데 val에 따로 받으니까 쉽게 풀어나갈 수 있었다!

그리고 xor 연산을 하려면 이진수로 바꾸고 해야하는줄 알았는데, 바로 xor 연산을 해도 적용이 된다는 점도 알게됐다.