보통
Single Number
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 유일수(nums):2 누적 = 03 반복 i = 0 … n-1:4 누적 = 누적 XOR nums[i] // 짝은 상쇄5 반환 누적
변수
- 누적
- 0
1 / 5누적 XOR 값을 0에서 시작합니다.
전부 XOR하면 짝지어 나온 수는 상쇄되고 한 번만 나온 수만 남는다.
왜 헷갈리는가
해시맵으로 개수를 세도 되지만 XOR은 공간 O(1)·한 줄로 끝난다. 'a^a=0, a^0=a'라는 XOR의 두 성질이 왜 답을 주는지가 처음엔 마법처럼 보인다.
핵심 아이디어
XOR은 교환·결합 법칙이 성립하고 같은 값끼리는 0으로 상쇄된다. 그래서 순서와 무관하게 전부 XOR하면 쌍들은 사라지고 홀로 남은 값만 살아남는다.
복잡도
시간 O(n)·공간 O(1). 해시맵/셋 풀이(O(n) 공간)보다 메모리가 압도적으로 낫다.
실무에서 어디에 쓰나
XOR 상쇄·비트 트릭은 저수준·대용량 처리에서 실전 도구다.
- 무결성: 패리티/체크섬(XOR)·RAID 5 패리티 복구
- 누락 탐지: 두 집합의 대칭차(한쪽에만 있는 원소) 빠른 검출
- 임베디드: 메모리 없이 값 교환(a^=b^=a^=b), 토글 플래그
- 암호·해시: XOR은 스트림 암호·마스킹의 기본 연산
흔한 실수
'모두 두 번, 하나만 한 번' 전제가 깨지면 성립하지 않음(세 번 나오면 다른 접근). 부동소수엔 못 씀.
기억할 것
- a^a=0, a^0=a 두 성질이 전부.
- O(1) 공간의 대표 비트 트릭.
- 패리티·대칭차·마스킹에 실전 사용.
- 전제(짝+하나)가 깨지면 다른 접근.