C++로 자기 자신을 제외한 나머지 요소들의 XOR 값으로 새 배열 구성하기

양수로만 이루어진 크기 n의 배열 A[]가 있다고 가정해 보겠습니다. 이때 새로운 배열 B를 만들어야 하며, 각 요소 B[i]는 A[i] 자기 자신을 제외한 A[]의 나머지 모든 요소들의 XOR 값이 되어야 합니다.

예를 들어 A = [2, 1, 5, 9]라면, 결과는 B = [13, 14, 10, 6]이 됩니다.

접근 방법

이 문제는 전체 XOR 값을 단 한 번만 계산하는 아이디어로 효율적으로 해결할 수 있습니다. 먼저 배열 A의 모든 요소를 XOR한 값을 변수 x에 저장합니다. 그다음 각 요소 A[i]에 대해 B[i] = x XOR A[i]를 계산하면 됩니다.

이 방법이 작동하는 이유는 XOR 연산의 성질 때문입니다. 임의의 값 v에 대해 v XOR v = 0이라는 성질이 있으므로, 전체 XOR 값인 x에 다시 A[i]를 XOR하면 A[i] 자기 자신은 상쇄되고, 결국 A[i]를 제외한 나머지 요소들의 XOR 값만 남게 됩니다.

이 알고리즘은 두 번의 선형 순회만 필요하므로 시간 복잡도가 O(n)이며, 추가 배열 없이 제자리(in-place)에서 처리할 수 있어 공간 측면에서도 매우 효율적입니다.

예제 코드

#include <iostream>
using namespace std;
void findXOR(int A[], int n) {
   int x = 0;
   for (int i = 0; i < n; i++)
      x ^= A[i];
   for (int i = 0; i < n; i++)
      A[i] = x ^ A[i];
}
int main() {
   int A[] = {2, 1, 5, 9};
   int n = sizeof(A) / sizeof(A[0]);
   cout << "원래 요소들: ";
   for (int i = 0; i < n; i++)
      cout << A[i] << " ";
   cout << endl;
   cout << "XOR 변환 후 요소들: ";
   findXOR(A, n);
   for (int i = 0; i < n; i++)
      cout << A[i] << " ";
}

실행 결과

원래 요소들: 2 1 5 9
XOR 변환 후 요소들: 13 14 10 6