문제 링크

내 코드

다 XOR하면 0인지 확인

0ms, 263.86MB

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        int all{};
        for(int n : derived) all ^= n;

        if(all == 0) return true;
        else return false;
    }
};

Solution

Approach 1: Simulation

• 69ms, 290.00MB
• Complexity
  • Let $n$ be the size of the derived array.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        // Create an original array initialized with 0.
        vector<int> original = {0};
        for (int i = 0; i < derived.size(); i++) {
            original.push_back((derived[i] ^ original[i]));
        }
        // Store the validation results in checkForZero and checkForOne
        // respectively.
        bool checkForZero = (original[0] == original[original.size() - 1]);
        original = {1};
        for (int i = 0; i < derived.size(); i++) {
            original.push_back((derived[i] ^ original[i]));
        }
        bool checkForOne = (original[0] == original[original.size() - 1]);

        return checkForZero | checkForOne;
    }
};

GPT (o3-mini-high)

이 코드는 주어진 derived 배열을 기반으로, 원래의 배열(original)이 존재하는지 판별하는 문제를 해결합니다.
문제의 조건은 다음과 같습니다.

원래의 배열 original이 존재하여,
모든 $0 \leq i < n$에 대해
$\text{derived}[i] = \text{original}[i] \oplus \text{original}[(i+1) \bmod n]$
를 만족하는 경우, 해당 original 배열은 유효(valid)하다고 볼 수 있습니다.

특히, 원형으로 연결되어 있으므로 $\text{original}[n] = \text{original}[0]$여야 합니다.

코드에서는 original 배열을 복원하는 과정을 두 가지 경우(초기값을 0 또는 1로 설정)로 시도하여,
하나라도 $\text{original}[n] == \text{original}[0]$를 만족하면 유효한 배열이 존재한다고 판단합니다.

---

코드 동작 상세 설명

1. 첫 번째 시도: original[0] = 0

vector<int> original = {0};
for (int i = 0; i < derived.size(); i++) {
    original.push_back( derived[i] ^ original[i] );
}

• 원리:
  문제의 정의에 따라, $\text{derived}[i] = \text{original}[i] \oplus \text{original}[i+1]$
  이므로, $\text{original}[i+1] = \text{derived}[i] \oplus \text{original}[i]$ 로 원래 배열을 복원할 수 있습니다.

• 과정:

  • 먼저, original 배열의 첫 번째 원소를 0으로 초기화합니다.
  • 반복문을 돌면서, 각 $i$에 대해
    $\text{original}[i+1] = \text{derived}[i] \oplus \text{original}[i]$
    를 계산하여 original 배열에 추가합니다.

• 검증:
  반복문이 끝나면, 복원된 배열의 마지막 원소는 $\text{original}[n]$가 됩니다.
  원형 배열의 조건에 따라 $\text{original}[n]$는 $\text{original}[0]$와 같아야 합니다.
  이를 통해 첫 번째 경우의 결과를 확인합니다.

bool checkForZero = (original[0] == original[original.size() - 1]);

• checkForZero는 초기값 0으로 복원한 경우 $\text{original}[n] == \text{original}[0]$인지 여부를 나타냅니다.

---

2. 두 번째 시도: original[0] = 1

original = {1};
for (int i = 0; i < derived.size(); i++) {
    original.push_back( derived[i] ^ original[i] );
}

• 원리 및 과정은 첫 번째 시도와 동일합니다.
  단, 이번에는 original 배열의 첫 번째 원소를 1로 초기화하여 복원합니다.

• 검증:
  복원 후,

  bool checkForOne = (original[0] == original[original.size() - 1]);

  를 통해 초기값 1로 복원한 경우 $\text{original}[n] == \text{original}[0]$ 인지 확인합니다.

---

3. 최종 결과 반환

return checkForZero | checkForOne;

• 두 경우 중 하나라도 조건을 만족하면 유효한 original 배열이 존재한다는 의미입니다.
• 여기서 | 연산자는 논리 OR (또는 비트 OR로도 사용되지만, 두 불리언 값에 대해서는 동일한 효과를 냅니다.)
• 따라서, checkForZero 또는 checkForOne 중 하나라도 참이면 함수는 true를 반환합니다.

---

결론

• 아이디어:
  주어진 derived 배열에서,
  원래 배열을 $\text{original}[i+1] = \text{derived}[i] \oplus \text{original}[i]$ 관계를 통해 복원할 수 있습니다.
  단, 원형 관계 $(\text{original}[n] == \text{original}[0])$를 만족해야 하므로,
  초기값을 0과 1 두 가지 경우로 시도하여 유효성을 확인합니다.

• 시간 복잡도:
  $O(n)$ — derived 배열의 길이에 비례하여 복원 과정을 진행합니다.

이와 같이, 코드에서는 두 가지 초기값을 시도하여 하나라도 원형 조건을 만족하면 유효한 배열이 존재한다고 판단합니다.

Approach 2: Optimized Simulation

• 27ms, 289.83MB
• Complexity
  • Let $n$ be the size of the derived array.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(n)$

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        // Initialize the original array with 0 as the first element.
        vector<int> original = {0};

        // Generate the original array based on derived and original[0] = 0.
        for (int i = 0; i < derived.size(); i++) {
            original.push_back((derived[i] ^ original[i]));
        }

        // Check if the array is valid by comparing the first and last elements.
        return original[0] == original[original.size() - 1];
    }
};

GPT (o3-mini-high)

이 코드는 주어진 derived 배열로부터 원래의 배열(original)이 존재하는지 판별하는 문제를 해결합니다.
문제의 조건은 다음과 같습니다:

• 원래 배열의 각 인덱스에 대해
  $\text{derived}[i] = \text{original}[i] \oplus \text{original}[i+1] \quad \text{(0 ≤ i < n)}$
• 배열이 원형(circular)으로 연결되어 있으므로,
  $\text{original}[n] = \text{original}[0]$여야 합니다.

코드에서는 original[0] 를 0으로 고정하고,
주어진 관계를 이용하여 나머지 원소들을 복원한 뒤,
마지막 원소가 첫 번째 원소와 일치하는지 확인합니다.
일치하면 유효한 배열이 존재한다고 판단하여 true를,
그렇지 않으면 false를 반환합니다.

---

코드 설명

1. 원래 배열의 초기값 설정

vector<int> original = {0};

• original 배열을 선언하고,
  원래 배열의 첫 번째 원소를 0으로 초기화합니다.
• 문제에서는 **original[0]**의 값이 무엇이든 상관없지만,
  원래 배열의 존재 여부를 판단하기 위해 임의의 값(여기서는 0)을 선택합니다.

---

2. 원래 배열 복원

for (int i = 0; i < derived.size(); i++) {
    original.push_back((derived[i] ^ original[i]));
}

• 문제에서 주어진 관계
  $\text{derived}[i] = \text{original}[i] \oplus \text{original}[i+1]$
  를 이용하여,
  $\text{original}[i+1] = \text{derived}[i] \oplus \text{original}[i]$로 original 배열을 순차적으로 복원합니다.
• 반복문은 derived 배열의 모든 원소에 대해 실행됩니다.
• 각 단계에서
  • 현재 원소 original[i] 와 derived[i] 의 XOR 결과를 계산하여,
  • 이를 original[i+1] 로 배열에 추가합니다.

---

3. 원형 조건 검증

return original[0] == original[original.size() - 1];

• 배열이 원형으로 연결되어 있으므로,
  복원한 original 배열의 마지막 원소와 첫 번째 원소가 같아야 합니다.
• 만약 $\text{original}[0] == \text{original}[n]$라면,
  주어진 derived 배열에 해당하는 유효한 original 배열이 존재하는 것이므로 true를 반환합니다.
• 그렇지 않으면, false를 반환합니다.

---

요약

1. original[0] 를 0으로 초기화합니다.

2. 각 $i$에 대해 $\text{original}[i+1] = \text{derived}[i] \oplus \text{original}[i]$를 이용해 original 배열을 복원합니다.

3. 복원한 배열의 마지막 원소가 첫 번째 원소와 같으면,
   조건$(\text{original}[n] = \text{original}[0])$을 만족하므로 유효한 배열이 존재한다고 판단합니다.

이 방식은 문제의 관계식을 그대로 활용하여 O(n) 시간에 유효성을 검사합니다.

Approach 3: Cumulative XOR

• 0ms, 263.90MB
• Complexity
  • Let $n$ be the size of the derived array.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        int XOR = 0;
        for (auto element : derived) {
            XOR = XOR ^ element;
        }
        return XOR == 0;
    }
};

GPT (o3-mini-high)

이 코드는 주어진 derived 배열이 유효한 배열에서 파생되었는지 판별하기 위해, 배열의 모든 원소를 XOR한 값이 0인지 확인합니다. 문제의 배경은 다음과 같습니다.

---

문제 배경

원래 배열 original이 있을 때,
derived 배열은 다음과 같이 정의됩니다:

• $\text{derived}[i] = \text{original}[i] \oplus \text{original}[(i+1) \bmod n]$

여기서 $\oplus$는 XOR 연산을 의미하며, 원형 배열이므로 마지막 원소와 첫 번째 원소도 연결됩니다.

XOR 연산의 성질에 따르면, 동일한 값끼리 XOR 하면 0이 됩니다.
원래 배열에서 각 원소는 두 번 XOR에 참여하게 됩니다.
즉,
$\begin{aligned} \text{derived}[0] \oplus \text{derived}[1] \oplus \cdots \oplus \text{derived}[n-1] \\ = (\text{original}[0] \oplus \text{original}[1]) \oplus (\text{original}[1] \oplus \text{original}[2]) \oplus \cdots \oplus (\text{original}[n-1] \oplus \text{original}[0]) \\ = \text{original}[0] \oplus \text{original}[1] \oplus \text{original}[1] \oplus \text{original}[2] \oplus \cdots \oplus \text{original}[n-1] \oplus \text{original}[0] \\ = 0. \end{aligned}$

따라서, 유효한 derived 배열이라면 모든 원소의 XOR 결과는 0이어야 합니다.

---

코드 설명

bool doesValidArrayExist(vector<int>& derived) {
    int XOR = 0;
    for (auto element : derived) {
        XOR = XOR ^ element;
    }
    return XOR == 0;
}

1. 초기화

   • int XOR = 0;
     모든 원소를 XOR할 때 결과를 저장할 변수를 0으로 초기화합니다.

2. 배열 순회 및 XOR 누적

   • for (auto element : derived) { XOR = XOR ^ element; }
     배열의 각 원소에 대해 XOR 연산을 수행합니다.
     XOR 연산의 특성상 같은 숫자가 두 번 등장하면 상쇄되어 0이 되므로,
     유효한 derived 배열에서는 모든 원소가 짝수 번 등장하는 효과를 내어 최종 결과가 0이 됩니다.

3. 검증 및 결과 반환

   • return XOR == 0;
     누적한 XOR 값이 0이면 유효한 배열에서 파생된 것이라고 판단하고 true를 반환하고,
     그렇지 않으면 false를 반환합니다.

---

결론

이 코드는 derived 배열에 있는 모든 원소를 XOR한 값이 0인지 검사하여,
원래의 배열이 존재할 수 있는지 (즉, derived 배열이 유효한지) 판별합니다.
XOR 연산의 특성을 활용한 매우 간단하고 효율적인 풀이입니다.

Approach 4: Sum Parity

• 0ms, 263.80MB
• Complexity
  • Let $n$ be the size of the derived array.
  • Time Complexity: $O(n)$
  • Space Complexity: $O(1)$

class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        int sum = accumulate(derived.begin(), derived.end(), 0);
        return sum % 2 == 0;
    }
};

GPT (o3-mini-high)

이 코드는 주어진 derived 배열의 모든 원소의 합을 구한 후, 그 합이 짝수인지 확인하여 유효한 배열이 존재하는지 판별합니다.

배경

문제의 조건은 다음과 같습니다.
원래의 배열 original에서 파생된 derived 배열은 아래 관계를 만족해야 합니다:

$\text{derived}[i] = \text{original}[i] \oplus \text{original}[(i+1) \bmod n]$

여기서 $\oplus$는 XOR 연산입니다.
이 관계를 원형으로 모두 XOR하면, 모든 original의 원소가 두 번 XOR에 참여하여 서로 상쇄되므로,
derived 배열의 모든 원소를 XOR한 결과는 0이 되어야 합니다.

XOR의 성질:
이진 값(0 또는 1)에서 XOR 연산은 사실 각 원소의 홀짝 여부(패리티)를 나타냅니다.
예를 들어, $0 \oplus 1 \oplus 1 = 0$이고, 이는 배열에 1이 짝수 개 있다는 것을 의미합니다.

즉, derived 배열이 유효하려면 배열 내의 1의 개수가 짝수여야 합니다.

코드 동작

1. 합계 계산

   int sum = accumulate(derived.begin(), derived.end(), 0);

   • accumulate 함수는 <numeric> 헤더에 정의되어 있으며,
     derived 배열의 모든 원소를 더해 sum에 저장합니다.
   • 만약 derived 배열의 원소가 0과 1로 이루어져 있다면,
     sum은 배열 내 1의 개수를 나타냅니다.

2. 짝수 여부 판별

   return sum % 2 == 0;

   • sum % 2 연산을 통해 1의 개수가 짝수인지(즉, 나머지가 0인지) 확인합니다.
   • 짝수라면 유효한 derived 배열의 조건(모든 원소의 XOR 결과가 0)을 만족하므로 true를 반환합니다.
   • 홀수라면 조건에 어긋나므로 false를 반환합니다.

결론

이 코드는 derived 배열이 0과 1로 구성되어 있을 때,
1의 총 개수가 짝수인지(즉, 배열 전체의 XOR 결과가 0인지)를 검사하여
유효한 원래 배열 original이 존재하는지를 판단합니다.

• 시간 복잡도: $O(n)$ — 배열의 모든 원소를 한 번씩 합산합니다.
• 핵심 아이디어: 배열의 패리티(홀짝성)를 합계를 통해 확인함으로써 XOR 결과를 간단하게 판별할 수 있다는 점입니다.