문제 이해하기
두 개의 배열 arr1과 arr2가 주어졌다고 가정해 봅시다. 여기서 어떤 리스트의 'XOR 합'이란 리스트에 포함된 모든 원소를 비트 단위 XOR 연산한 결과를 의미합니다. 만약 리스트에 원소가 하나뿐이라면, 그 원소 자체가 곧 XOR 합이 됩니다.
이제 모든 인덱스 쌍 (i, j)(단, 0 <= i < arr1의 길이, 0 <= j < arr2의 길이)에 대해 arr1[i]와 arr2[j]의 비트 단위 AND 연산 결과로 이루어진 새로운 리스트를 생각해 보겠습니다. 우리가 구해야 하는 값은 바로 이 리스트의 XOR 합입니다.
예시
입력이 arr1 = [5, 3, 4], arr2 = [2, 6]인 경우를 살펴보겠습니다. 먼저 모든 쌍의 AND 결과는 다음과 같습니다.
[5 AND 2, 5 AND 6, 3 AND 2, 3 AND 6, 4 AND 2, 4 AND 6] = [0, 4, 2, 2, 0, 4]
이 리스트의 XOR 합을 계산하면 0 XOR 4 XOR 2 XOR 2 XOR 0 XOR 4 = 0이므로, 최종 출력값은 0이 됩니다.
효율적인 접근 방법
모든 쌍을 하나씩 계산하는 방법은 시간 복잡도가 O(n×m)으로 비효율적입니다. 대신 비트 연산의 분배 법칙을 활용하면 훨씬 빠르게 문제를 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
(arr1의 모든 원소의 XOR) AND (arr2의 모든 원소의 XOR) = 모든 (arr1[i] AND arr2[j]) 쌍의 XOR 합
따라서 해결 절차는 다음과 같습니다.
- xor1을 0으로 초기화합니다.
- xor2를 0으로 초기화합니다.
- arr1의 각 원소 a에 대해 xor1 := xor1 XOR a를 수행합니다.
- arr2의 각 원소 a에 대해 xor2 := xor2 XOR a를 수행합니다.
- 최종적으로 xor1 AND xor2를 반환합니다.
파이썬 구현 예제
아래 코드를 통해 실제 동작을 확인해 보겠습니다.
def solve(arr1, arr2):
xor1 = 0
xor2 = 0
for a in arr1:
xor1 ^= a
for a in arr2:
xor2 ^= a
return xor1 & xor2
arr1 = [5, 3, 4]
arr2 = [2, 6]
print(solve(arr1, arr2))
입력
[5, 3, 4], [2, 6]
출력
0
복잡도 분석
이 알고리즘은 각 배열을 한 번씩만 순회하므로 시간 복잡도는 O(n + m)입니다. 또한 추가적인 저장 공간 없이 두 개의 변수만 사용하므로 공간 복잡도는 O(1)로 매우 효율적입니다. 덕분에 배열의 크기가 커지더라도 안정적인 성능을 기대할 수 있습니다.