문제 개요
배열 enc가 하나 주어져 있다고 가정해 보겠습니다. 처음 n개의 양의 정수(n은 홀수)로 이루어진 순열(permutation) 배열 perm이 존재하며, 이 배열은 길이가 n-1인 배열 enc로 다음 규칙에 따라 인코딩되어 있습니다.
enc[i] = perm[i] XOR perm[i+1]
즉, 인접한 두 원소를 XOR한 결과가 차례대로 enc에 저장된 형태입니다. 우리가 해야 할 일은 이렇게 압축된 정보만으로 원래의 순열 배열 perm을 복원하는 것입니다.
예시
입력이 enc = [2, 5, 6, 3]이라면 출력은 [7, 5, 0, 6, 5]가 됩니다. 실제로 계산해 보면 다음과 같습니다.
- 7 XOR 5 = 2
- 5 XOR 0 = 5
- 0 XOR 6 = 6
- 6 XOR 5 = 3
해결 접근 방식
이 문제는 XOR 연산의 기본 성질만 이해하면 선형 시간 O(n) 안에 해결할 수 있습니다. 활용되는 핵심 성질은 다음과 같습니다.
- x XOR x = 0 : 같은 값을 두 번 XOR하면 서로 상쇄되어 사라집니다.
- x XOR 0 = x : 0과의 XOR은 원래 값을 그대로 유지합니다.
- XOR은 교환 법칙과 결합 법칙이 성립하므로, 연산 순서를 마음대로 바꿀 수 있습니다.
1단계: 첫 번째 원소 perm[0] 구하기
perm은 1부터 n+1까지의 모든 정수를 정확히 한 번씩 포함하므로, 전체 원소를 모두 XOR한 값은 곧 1부터 n+1까지의 수를 XOR한 값과 같습니다.
한편 enc의 홀수 인덱스 원소들만 모아 XOR하면 (perm[1] XOR perm[2]) XOR (perm[3] XOR perm[4]) XOR ... 형태가 되어, 결국 perm[0]을 제외한 나머지 원소 전체의 XOR 값과 동일합니다. 따라서 다음 식으로 첫 번째 원소를 바로 구할 수 있습니다.
perm[0] = (1 XOR 2 XOR ... XOR (n+1)) XOR (enc[1] XOR enc[3] XOR ...)
2단계: 나머지 원소 복원하기
첫 번째 원소를 알아냈다면 나머지는 매우 간단합니다. 관계식 enc[i] = perm[i] XOR perm[i+1]의 양변에 perm[i]를 한 번 더 XOR하면 perm[i]는 상쇄되고 perm[i+1]만 남기 때문에, 다음 점화식으로 왼쪽부터 차례대로 복원할 수 있습니다.
perm[i+1] = perm[i] XOR enc[i]
알고리즘 단계
- n := enc의 크기
- result := 크기가 (n+1)인 배열을 생성하고 0으로 초기화
- x := 0
- i가 1부터 n+1까지 증가하며 반복:
- x := x XOR i
- result[0] := x
- i가 1부터 n까지 2씩 증가하며 반복:
- result[0] := result[0] XOR enc[i]
- i가 1부터 n까지 증가하며 반복:
- result[i] := result[i-1] XOR enc[i-1]
- result 반환
파이썬 구현 예제
아래 코드를 실행하면 위에서 설명한 과정을 직접 확인할 수 있습니다.
def solve(enc):
n = len(enc)
result = [0] * (n + 1)
x = 0
for i in range(1, n + 2):
x ^= i
result[0] = x
for i in range(1, n + 1, 2):
result[0] ^= enc[i]
for i in range(1, n + 1):
result[i] = result[i - 1] ^ enc[i - 1]
return result
enc = [2, 5, 6, 3]
print(solve(enc))
실행 결과
입력:
[2,5,6,3]
출력:
[7, 5, 0, 6, 5]
마무리
이 문제의 핵심은 XOR의 자기 역원(self-inverse) 성질입니다. 같은 값이 짝수 번 등장하면 모두 사라지고 홀수 번 등장한 값만 남는다는 점을 활용하면, 전체 XOR 값과 부분 XOR 값의 차이만으로 숨겨진 원소를 정확히 역산할 수 있습니다. 시간 복잡도는 O(n), 공간 복잡도는 O(n)으로 매우 효율적이며, 비트 연산의 성질을 응용하는 대표적인 알고리즘 문제이기도 합니다.