[코테연습] 2683. Neighboring Bitwise XOR

https://leetcode.com/problems/neighboring-bitwise-xor/description/?envType=daily-question&envId=2025-01-17

 

문제 타입

• 배열과 비트 연산 문제.
• 순환 배열 구조를 이해하고 XOR 연산의 특성을 활용하는 문제.
• 주어진 조건(derived[i] = original[i] ⊕ original[i+1])을 만족하는 배열의 존재 가능성을 판단.

---

문제 분석

• 조건:
  • 배열 original의 인접한 두 원소 간의 XOR 결과가 derived 배열로 주어짐.
  • 순환 배열 구조이므로 마지막 원소와 첫 번째 원소도 XOR 관계를 가짐 (original[n-1] ⊕ original[0]).
• 목표:
  • 주어진 derived 배열이 특정 original 배열에서 파생될 수 있는지 확인.
• 중요한 관찰:
  • XOR 연산의 특성상, 배열의 모든 값을 XOR하면 중간 값이 상쇄됨: derived[0]⊕derived[1]⊕⋯⊕derived[n−1]=0derived[0] ⊕ derived[1] ⊕ \dots ⊕ derived[n-1] = 0derived[0]⊕derived[1]⊕⋯⊕derived[n−1]=0
    • 이 조건이 만족되면, 문제에서 요구하는 original 배열이 존재함.

---

문제 풀이

1. XOR 연산 활용:
   • XOR의 특성:
     • A ⊕ A = 0: 같은 값은 상쇄됨.
     • A ⊕ 0 = A: 0은 값에 영향을 미치지 않음.
   • derived 배열의 모든 값을 XOR한 결과가 0이면, 조건을 만족하는 original 배열이 존재.
2. 풀이 과정:
   • derived 배열의 모든 요소를 XOR 연산으로 누적합 계산.
   • 결과값이 0이면 true, 그렇지 않으면 false를 반환.

 

- java

 

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int xorSum = 0;

        // XOR 특성을 활용하여 derived 배열을 확인
        for (int value : derived) {
            xorSum ^= value;
        }

        // XOR 합이 0이면 valid 배열이 존재함
        return xorSum == 0;
    }
}

 

 

- python

 

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        xor_sum = 0
        for num in derived :
            xor_sum ^= num
        if xor_sum == 0 : 
            return True
        else :
            return False