정수로 이루어진 배열이 주어졌을 때, 단 하나의 요소만 홀수 번 나타나고 나머지 모든 요소는 짝수 번 나타난다고 가정해 보겠습니다. 이때 우리의 목표는 단 한 번의 반복으로 해당 요소를 찾아내는 것입니다.
예시 배열은 다음과 같습니다.
[1, 4, 3, 4, 2, 3, 2, 7, 8, 8, 9, 7, 9]
XOR(^) 연산자의 원리 이해하기
이 문제를 해결하기 전에 먼저 비트 연산자인 XOR(^)에 대해 간단히 알아보겠습니다.
XOR 연산자는 두 피연산자가 서로 다를 때 TRUE(1)를 반환하고, 두 피연산자가 같을 때 FALSE(0)를 반환합니다.
XOR 연산자의 진리표
0 ^ 0 → 0 0 ^ 1 → 1 1 ^ 0 → 1 1 ^ 1 → 0
이 동작 방식을 자세히 살펴보면 흥미로운 사실을 발견할 수 있습니다. XOR 연산자를 완전히 동일한 값에 적용하면(예: 12^12) 항상 0을 반환합니다. 즉, 짝수 번 나타나는 값들을 서로 상쇄하여 제거하는 데 활용할 수 있습니다. 이것이 바로 우리가 원하는 동작입니다.
짝수 번 등장하는 요소들은 XOR 과정에서 모두 0으로 상쇄되고, 결국 홀수 번 나타나는 유일한 요소만 남게 됩니다.
코드 구현 예제
이 원리를 코드로 작성하면 다음과 같습니다.
const sampleArray = [1, 4, 3, 4, 2, 3, 2, 7, 8, 8, 9, 7, 9]; console.log(sampleArray.reduce((a, b) => a ^ b));
reduce() 메서드가 배열의 각 요소를 순회하면서 누적값에 XOR 연산을 적용합니다. 이 과정에서 짝수 번 나타나는 요소들은 서로 상쇄되어 사라지고, 최종적으로 홀수 번 나타나는 유일한 요소만 반환됩니다.
실행 결과
콘솔 출력 결과는 다음과 같습니다.
1
정리
XOR 연산자의 자기 역원 성질(a ^ a = 0)을 활용하면 추가적인 메모리 없이 O(n) 시간 복잡도로 문제를 해결할 수 있습니다. 해시맵이나 객체를 사용해 빈도를 세는 방식보다 훨씬 효율적이며, 코드도 한 줄로 간결하게 작성할 수 있다는 장점이 있습니다.