문제 개요
n개의 요소로 이루어진 어떤 배열을 복원해야 하는 상황을 가정해 봅시다. 다만 우리가 알고 있는 정보는 실제 배열에서 인접한 두 요소끼리 XOR 연산한 값들과 배열의 첫 번째 요소뿐입니다.
예를 들어 실제 배열이 a, b, c, d, e, f라면, 주어진 배열은 다음과 같습니다.
a^b, b^c, c^d, d^e, e^f
해결 아이디어
핵심은 XOR 연산의 자기 역원(self-inverse) 성질입니다. 즉, 임의의 값 x에 대해 다음이 항상 성립합니다.
- x ^ x = 0
- x ^ 0 = x
이 성질 때문에 (a ^ b) ^ a = b가 됩니다. 따라서 첫 번째 요소 a가 주어져 있다면, 나머지 모든 요소를 차례대로 유도할 수 있습니다.
- 두 번째 요소: b = a ^ arr[0]
- 세 번째 요소: c = b ^ arr[1]
- 이후 요소도 같은 방식으로 반복
일반화하면 actual[i + 1] = arr[i] ^ actual[i] 점화식으로 표현할 수 있습니다.
C++ 구현 예제
#include<iostream>
using namespace std;
void findActualElements(int a, int arr[], int n) {
int actual[n + 1];
actual[0] = a; // 첫 번째 요소는 입력으로 주어짐
for (int i = 0; i < n; i++) {
// 인접 XOR 값과 이전 요소를 XOR하여 다음 요소 복원
actual[i + 1] = arr[i] ^ actual[i];
}
for (int i = 0; i < n + 1; i++)
cout << actual[i] << " ";
}
int main() {
int arr[] = { 12, 5, 26, 7 }; // 인접 요소들의 XOR 값 배열
int n = sizeof(arr) / sizeof(arr[0]);
int a = 6; // 실제 배열의 첫 번째 요소
findActualElements(a, arr, n);
}실행 결과
6 10 15 21 18
동작 과정 살펴보기
- actual[0] = 6 (주어진 첫 번째 요소)
- actual[1] = 12 ^ 6 = 10
- actual[2] = 5 ^ 10 = 15
- actual[3] = 26 ^ 15 = 21
- actual[4] = 7 ^ 21 = 18
최종적으로 원본 배열 {6, 10, 15, 21, 18}이 정확히 복원된 것을 확인할 수 있습니다.
시간 및 공간 복잡도
- 시간 복잡도: O(n) — 배열을 한 번만 순회하면 됩니다.
- 공간 복잡도: O(n) — 결과를 저장할 배열이 필요하며, 출력만 한다면 O(1)로 최적화할 수도 있습니다.