2683. Neighboring Bitwise XOR

https://leetcode.com/problems/neighboring-bitwise-xor/description/

 

이번 문제는 생각보다 간단해서 힘이 빠졌다.

정말 어렵게 고민했었는데  사실은 아주 쉽게 해결된다는 사실을 깨달았다.

길이 n으로 유도된 0-인덱스 배열은 길이 n의 이진 배열 original에서
인접한 값의 비트 단위 XOR(⊕)을 계산하여 유도됩니다.

구체적으로, [0, n - 1] 범위의 각 인덱스 i에 대해
i = n - 1이면 derived[i] = original[i] ⊕ original[0]입니다.
그렇지 않으면 derived[i] = original[i] ⊕ original[i + 1]입니다.

주어진 배열 derived에서, 여러분의 과제는
derived를 형성할 수 있는 유효한 이진 배열 original이존재하는지 여부를 확인하는 것입니다.

그러한 배열이 있으면 true를 반환하고 그렇지 않으면 false를 반환합니다.
이진 배열은 0과 1만 포함하는 배열입니다.

예제 1:
입력: derived = [1,1,0]
출력: true
설명: derived를 제공하는 유효한 original 배열은 [0,1,0]입니다.
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0

예제 2:
입력: derived = [1,1]
출력: true
설명: derived를 제공하는 유효한 original 배열은 [0,1]입니다.
derived[0] = original[0] ⊕ original[1] = 1
derived[1] = original[1] ⊕ original[0] = 1

예제 3:
입력: derived = [1,0]
출력: false
설명: derived를 제공하는 유효한 original 배열이 없습니다.

제약 조건:
n == derived.length 1 <= n <= 105 derived의 값은 0 또는 1입니다.

 

요약하면 derived 배열이 주어지는데 이 배열의 값을 생성할 수 있는XOR 배열의 존재 여부를 묻는 문제다.

 

난 이 문제를 정말로 어렵게 생각했다

왜냐면 [1,1,0] 이 주어지면 1을  만들기 위해서는 0,1이 필요하고

그럼 [0,1] [1,0],[0,0] 이렇게 3개의 경우의 수가 생기는데 이걸 어떻게 합친단 말인가

 

이것저것 고민했지만 결국 답은 정말 간단했다.

주어진 배열에서 1의 개수가 짝수인 경우에만 정답이라는 것이다.그  예시를 들어보자면 

입력: derived = [1,1,0]
출력: true
설명: derived를 제공하는 유효한 original 배열은 [0,1,0]입니다.
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 0 = 1
derived[2] = original[2] ⊕ original[0] = 0 ⊕ 0 = 0


입력: derived = [1,0,0]
출력: false
derived[0] = original[0] ⊕ original[1] = 0 ⊕ 1 = 1
derived[1] = original[1] ⊕ original[2] = 1 ⊕ 1 = 0
derived[2] = original[2] ⊕ original[0] = 1 ⊕ 1 = 0

 

두번째 입력인 [1,0,0] 의 경우에 먼저 첫번째 1을 만족하기 위해서는 [0,1] 또는 [1,0] 이 필요하다. 

다음으로 0을 만족하려면 [0,0] 또는 [1,1] / 마지막 0 또한 [0,0] 또는 [1,1] 이 필요하다

 

하지만 [0,1]로 시작했다면 [0,1,1]이 되어야 하고 이 경우 마지막 XOR은 [1,0]이 되어 0을 만들수가 없다

고로 배열에서 주어진 수에서 1의 개수가 짝수인 경우만 XOR이 성립된다.

 

이제 문제 해결 방법을 알았으니 이를 적용하여 코드를 짜면 된다.

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        boolean result = false;
        int count = 0;
        
        for(int d : derived){
            if(d == 1){
                count++;
            }
        }

        if(count%2 == 0){
            result = true;
        }

        return result;
    }
}

 

위 코드는 요소의 값이 1이면 count의 값을 올리고

마지막에  카운트값을 2로 나눈 나머지가 0이면  true를 반환한다.

 

쓸데없는 동작도 많고 시간복잡도가 꽤 높아서 더 간단하게 코드를 수정했다

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int count = 0;
        
        for(int d : derived){
            if(d == 1){
                count++;
            }
        }
        return count % 2 == 0;
    }
}

 

이번엔 if문을 하나로 묶어서 해결했다.

그런데도 별 차이가 안나길래 나보다 더 빠른 사람들의 코드를 한번 읽어보았다.

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int xor=0;
        for(int x:derived)
            xor^=x;
        return xor==0;
    }
}

 

이건 정말 신선한 충격이였다

간단하게 ^ (XOR) 을 이용해서 값이 0이 나오면 true를  반환하게 했다니

손으로 다시 계산해봐도 0이 나오면 true가 나왔다.

 

이외에도 다른 코드도 봤는데

class Solution {
    public boolean doesValidArrayExist(int[] derived) {
        int count = 0;
        
        for(int d : derived){
            count += d;
        }
        return count % 2 == 0;
    }
}

 

쓸데없는 if문을 아예 없애서 더 간단하게 짤 수 있었다.

 

이렇게 하니 런타임은 2ms 메모리는 63.75mb가 나왔다.

일단 원리만 이해하면 푸는건 시간 문제인것 같다.