문제 소개
이 문제에서는 n개의 원소로 이루어진 배열 A가 주어집니다. 우리가 해야 할 작업은 배열 A의 모든 원소 쌍(자기 자신과의 쌍 포함)의 합으로 구성된 크기 n×n의 새로운 배열 B를 생성하고, 배열 B에 있는 모든 값들의 XOR을 계산하여 출력하는 것입니다.
예제로 이해하기
입력 − A = (1, 4, 5)
출력 − 0
설명 −
B = (1+1, 1+4, 1+5, 4+1, 4+4, 4+5, 5+1, 5+4, 5+5)
B = (2, 5, 6, 5, 8, 9, 6, 9, 10)
모든 값의 XOR = 2^5^6^5^8^9^6^9^10 = 0
해결 접근 방법
이 문제를 효율적으로 해결하려면 XOR 연산의 몇 가지 핵심 성질을 활용해야 합니다.
첫 번째 성질은 같은 수끼리 XOR하면 결과가 0이라는 것입니다. 즉, x ^ x = 0이 항상 성립합니다.
새로 만들어진 배열 B를 자세히 살펴보면, a[i]+a[j]와 a[j]+a[i]처럼 순서만 다르고 실제 값은 동일한 원소들이 서로 짝을 이루어 존재합니다. 덧셈에는 교환 법칙이 적용되므로 두 값은 언제나 같고, 따라서 이런 쌍들을 XOR하면 모두 0이 됩니다.
결국 마지막까지 남는 원소는 a[i]+a[i], 즉 2×a[i] 형태의 값들뿐입니다. 따라서 배열 A의 모든 원소를 차례대로 XOR한 뒤, 그 결과에 2를 곱해주면 그것이 곧 최종 답이 됩니다.
이 방법의 시간 복잡도는 배열을 한 번만 순회하면 되므로 O(n)이며, n×n 크기의 배열을 실제로 만들 필요가 없어 메모리 면에서도 매우 효율적입니다.
구현 예제
위에서 설명한 알고리즘을 C++로 구현한 프로그램입니다.
#include <iostream>
using namespace std;
int findSumXor(int arr[], int n){
int XOR = 0 ;
for (int i = 0; i < n; i++) {
XOR = XOR ^ arr[i];
}
return XOR * 2;
}
int main(){
int arr[3] = { 2, 4, 7 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"배열 원소 쌍의 합에 대한 XOR 값: "<<findSumXor(arr, n);
return 0;
}
실행 결과
배열 원소 쌍의 합에 대한 XOR 값: 2
위 예제에서 배열 A = (2, 4, 7)의 각 원소를 XOR하면 2 ^ 4 ^ 7 = 1이 되고, 여기에 2를 곱한 2가 최종 출력값으로 나타납니다. 이처럼 XOR 연산의 성질만 잘 이해하면 복잡해 보이는 문제도 아주 간단하고 빠르게 해결할 수 있습니다.