문제 개요
주어진 배열과 목표 값 k가 있을 때, 배열의 모든 요소를 차례대로 XOR한 결과에 어떤 숫자 X를 추가로 XOR하면 그 최종 결과가 정확히 k가 되도록 하는 숫자 X를 찾는 것이 이번 튜토리얼의 목표입니다.
먼저 예시를 통해 문제를 살펴보겠습니다.
입력: arr[] = {1, 2, 3, 4, 5}, k = 10
출력: 11
설명: 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 11 = 10
입력: arr[] = {12, 23, 34, 56, 78}, k = 6
출력: 73이 문제를 해결하는 열쇠는 XOR 연산자가 가진 독특한 성질입니다. 바로 A ^ B = C일 때, A ^ C = B라는 성질입니다. 즉, XOR은 자기 역연산(self-inverse) 성질을 가지므로 이를 활용하면 아주 간단하게 답을 구할 수 있습니다.
해결 접근 방법
XOR의 위 성질을 활용하는 방법은 다음과 같습니다.
- 주어진 배열을 처음부터 끝까지 순회하면서 모든 요소의 XOR 합을 계산합니다.
- 계산된 XOR 합에 목표 값 k를 한 번 더 XOR합니다. 이것이 곧 우리가 찾고자 하는 답이 됩니다.
왜 이렇게 되는 걸까요? 배열 전체의 XOR 합을 S라고 하면, 우리가 원하는 것은 S ^ X = k를 만족하는 X입니다. XOR의 성질에 따라 양변에 다시 S를 XOR하면 X = S ^ k가 되기 때문입니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
int main() {
int arr[] = { 1, 2, 3, 4, 5 }; // 주어진 배열
int n = sizeof(arr) / sizeof(int); // 배열의 크기
int k = 10; // 주어진 목표 값 k
int answer = 0;
// 배열을 순회하며 XOR 합 계산
for (int i = 0; i < n; i++)
answer ^= arr[i];
answer ^= k; // k를 XOR하여 최종 답 도출
cout << answer << "\n"; // 결과 출력
return 0;
}
실행 결과
11
코드 동작 원리 상세 설명
위 코드의 동작 과정을 단계별로 살펴보겠습니다.
첫 번째 단계에서는 배열의 모든 요소를 하나씩 순회하면서 누적 XOR 값을 계산합니다. 예시 배열 {1, 2, 3, 4, 5}의 경우, 1 ^ 2 ^ 3 ^ 4 ^ 5의 결과가 저장됩니다.
두 번째 단계에서는 이렇게 구한 배열 전체의 XOR 합에 목표 값 k(=10)를 XOR 연산합니다. XOR의 자기 역연산 성질 덕분에 이 결과가 바로 배열의 XOR 합이 k가 되도록 만드는 숫자입니다.
시간 복잡도는 배열을 한 번만 순회하므로 O(n)이며, 공간 복잡도는 추가 변수 하나만 사용하므로 O(1)로 매우 효율적인 알고리즘입니다.
마무리
이번 튜토리얼에서는 주어진 배열의 XOR 합이 특정 값 k가 되도록 만드는 숫자를 찾는 문제를 해결했습니다. XOR 연산자의 A ^ B = C ⟺ A ^ C = B라는 성질을 활용하면 배열을 한 번만 순회해도 답을 구할 수 있다는 점이 핵심입니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 학습에 도움이 되기를 바랍니다.