[Java]XOR 이용하기
XOR의 진리표는 다음과 같다.
그럼 사용할 수 있는 경우를 보자.
Arrays.asList(1,1,2,2,3,3,5,5,4)위와 같은 List 가 있다.
list 안에는 중복되는 1,2,3,5 가 있을 때 중복되지 않는 4의 값만 가져오고 싶다.
이러한 알고리즘을 풀 때는 다양한 방법이 존재하지만 XOR을 이용해서 간단히 풀 수 있다.
private Integer Solution(List<Integer> integers) {
Integer i = 0;
for (Integer integer : integers) {
i ^=integer;
}
return i;
}이렇게 간단한 XOR 방법으로도 4를 추출할 수 있다.
좀 더 자세히 알아보자면
0 ^ 1 = 1
1 ^ 1 = 0
0 ^ 2 = 2
2 ^ 2 = 0
0 ^ 3 = 3
3 ^ 3 = 0
0 ^ 5 = 5
5 ^ 5 = 0
0 ^ 4 = 4 -> 최종 값
물론 List에 값이 정렬되어 있지 않아도 결과는 4로 같다 ex(1,2,4,2,1,5,3,3,5)
비트 값으로 보면( ->으로 보시면 됩니다) 초기값, 결괏값
|
000(0) 001(1) ---- 001(1) |
001(1) 010(2) ---- 011(3) |
011(3) 100(4) ---- 111(7) |
111(7) 010(2) ---- 101(5) |
101(5) 001(1) ---- 100(4) |
100(4) 101(5) ---- 001(1) |
001(1) 011(3) ---- 010(2) |
010(2) 011(3) ---- 001(1) |
001(1) 101(5) ---- 100(4) |
하지만 위와 같은 경우는 여태까지 개발을 하거나 공부하면서 쓴 경우는 별로 없던 거 같다.
왜냐하면 배열안에 짝이 맞지 않는 숫자가 단 하나만 존재한 것을 본 적이 없기 때문이다.
예를 들어
Arrays.asList(1,1,2,2,3,3,5,5,123,124)중복된 1,2,3,5 를 제외하고 123, 124 만 List로 담아서 Return 하고 싶다.
그래서 나는 왠만하면 이런 짝이 맞지 않는 경우에는 차라리 Set 이용해서 분류한다.
private Set<Integer> Solution(List<Integer> integers) {
Set<Integer> dup = new HashSet<>();
Set<Integer> noDup = new HashSet<>();
for (Integer integer : integers) {
if (dup.contains(integer)) {
noDup.remove(integer);
} else {
noDup.add(integer);
}
dup.add(integer);
}
return noDup;
}결괏값
