[99클럽 코테 스터디 27일차 TIL] ㅣLeetCode | 2433. Find The Original Array of Prefix Xor

27일차 array

Problem

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

 

Sol

XOR 연산으로 prefix된 배열을 통해서 원래의 배열을 찾는 문제

: 주어진 배열의 각 요소는 해당 위치까지의 누적 XOR 값을 나타내며, 원래 배열을 복원하는 것이 목적!

예시를 통해 문제 이해 & 해결 가능

 

해결 방법

👀 복원해야하는 origin_arr를 초기화하고, 반복문을 통해 prefix 배열의 값에 차례대로 접근하여 원래 값을 찾아내는 방식으로 해결하였습니다.

1. origin_arr : 찾으려고 하는 원래 배열
- 첫번째 원소는 pref의 첫 번째 원소와 동일

2. 반복문
- origin_arr[i] = pref[i] 번째와 pref[i-1] 번째 값을 XOR 한 값(^)

3. 정답

 

시간복잡도 O(n), 공간복잡도 O(n)

• 길이가 n인 'pref' 배열 순회 : O(n)
• 배열 'origin_arr'와 'pref'는 같은 크기 : O(n)

---

✔ Answer

class Solution:
    def findArray(self, pref: List[int]) -> List[int]:
        origin_arr = [0] * len(pref)
        
        origin_arr[0] = pref[0]
        
        for i in range(1, len(pref)):
            origin_arr[i] = pref[i] ^ pref[i-1]
            
        return origin_arr

---

💬 소감

굿