숨겨진 배열 arr에 음수가 아닌 정수 n개가 들어 있다고 가정해 봅시다. 이 배열은 길이가 n-1인 또 다른 배열 enc로 인코딩되며, 각 원소는 enc[i] = arr[i] XOR arr[i+1] 관계를 만족합니다. 인코딩된 배열 enc와 실제 배열의 첫 번째 원소인 정수 first가 주어졌을 때, 원래 배열을 복원하는 것이 이 문제의 목표입니다.
예를 들어, 입력이 enc = [8, 3, 2, 7], first = 4라면 출력은 [4, 12, 15, 13, 10]이 됩니다.
XOR 연산의 핵심 원리
이 문제는 XOR(배타적 논리합) 연산의 특성을 활용하면 쉽게 해결할 수 있습니다. XOR은 자기 자신이 역연산이 되는 독특한 성질을 가지고 있습니다.
a XOR b = c일 때,a XOR c = b그리고b XOR c = a가 성립합니다.같은 값을 두 번 XOR하면 원래 값으로 되돌아옵니다.
따라서 enc[i] = arr[i] XOR arr[i+1]이라는 관계식의 양변에 arr[i]를 XOR하면 arr[i+1] = arr[i] XOR enc[i]를 얻을 수 있습니다. 첫 번째 원소를 이미 알고 있으므로, 이 식을 반복적으로 적용하면 전체 배열을 순서대로 복원할 수 있습니다.
해결 접근 방법
결과 배열
arr을 첫 번째 원소first만 담은 상태로 초기화합니다.enc의 각 원소를 순회하면서 직전에 구한 값과 현재 인코딩 값을 XOR하여 다음 원소를 계산하고, 그 값을 배열 끝에 추가합니다.모든 원소를 처리한 후 완성된 배열
arr을 반환합니다.
Python 구현 예제
다음 코드를 통해 더 잘 이해해 보겠습니다.
def solve(enc, first):
arr = [first]
for i in range(len(enc)):
arr.append(arr[i] ^ enc[i])
return arr
enc = [8, 3, 2, 7]
first = 4
print(solve(enc, first))
입력
[8,3,2,7], 4
출력
[4, 12, 15, 13, 10]
동작 과정 살펴보기
위 예제가 어떻게 동작하는지 단계별로 확인해 보겠습니다.
시작: arr = [4]
i=0: 4 XOR 8 = 12 → arr = [4, 12]
i=1: 12 XOR 3 = 15 → arr = [4, 12, 15]
i=2: 15 XOR 2 = 13 → arr = [4, 12, 15, 13]
i=3: 13 XOR 7 = 10 → arr = [4, 12, 15, 13, 10]
복잡도 분석
이 알고리즘은 인코딩된 배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 공간 복잡도 또한 결과 배열을 저장하기 위해 O(n)이 필요합니다. 여기서 n은 원래 배열의 길이를 의미합니다.