리트 코드를 풀던 도중 도저히 풀리지 않는 문제가 있어 솔루션을 보았다.
결과적으로 내가 솔루션을 보길 잘 했다는 생각이 들었다.
내가 절대 알 수 없는 풀이였다.
대강 알고만 있던 XOR 연산을 어떻게 문제풀이에 사용할 수 있는지 기록하고자 한다
문제는 위와 같이, 숫자들의 배열이 주어지고 단 하나의 숫자를 제외하고는 전부 배열에 두개씩 들어가 있다. 이때, 단 하나로 존재하는 숫자를 찾아라 라는 문제이다.
여기서 독특한 것은, 시간복잡도 O(n) ""공간 복잡도를 O(1)"" 로 사용해야 하는 것이 조건이라는 것이다.
내가 생각해본 방법은 세가지였고,
하나는 brute force 방식의 탐색 --> 시간복잡도가 O(n^2) 로 탈락
둘째는 배열 정렬 --> 시간복잡도가 최소 O(nlogn) 이므로 탈락
셋째는 HashMap 을 사용하는 것 --> 공간복잡도가 O(n) 이므로 탈락이 되었다.
여기서부턴, 내가 아무리 고민을 해도 풀어낼 방법은 내가 떠올릴 수 없다고 판단 하였고 솔루션을 보아 XOR 을 사용한 문제풀이 방법을 알게 되었다.
XOR 이란?
XOR 은 비트연산자로, 같으면 0, 다르면 1을 반환한다.
여기서 내가 새롭게 알게 된 주요 특징은 바로
XOR 연산은 교환법칙, 결합법칙이 성립하며, 항등원은 0이다.
이 특징을 배열을 예로 들어서 설명해 보자면
int[] array = {1, 3, 1, 4, 6, 6, 4};XOR 연산
1 xor 1 = 0 -> 같으면 0을 반환
2 xor 0 = 2 -> 항등원 0, 따라서 2를 그대로 반환
1 xor 3 xor 1 xor 4 xor 6 xor 6 xor 4 의 식을 교환법칙 결합법칙을 사용하면 아래처럼 변한다.
(1 xor 1) xor (4 xor 4) xor (6 xor 6) xor 3 --> 그리고 이것은
0 xor 0 xor 0 xor 3 --> 이 되어 3을 리턴하게 된다.
XOR 연산을 사용하면 시간복잡도 O(N) 과 공간복잡도 O(1)로 위의 문제를 해결할 수 있었다.
