[Java] 1차원 배열에서 중복되지 않는 값 찾기

int[] arr = new int[]{1,2,1,3,3,2,4};

위와 같은 정수형 배열에서 중복되지 않는 4의 값을 가져오고 싶을 때,

1차원 배열에서 중복되지 않는 정수를 찾기 위해서는 XOR 연산이 필요하다.

명제 P	명제 Q	P ⊻ Q
1	1	0
1	0	1
0	1	1
0	0	0

[XOR 진리표]

 

 

XOR의 연산 과정을 살펴보면, 다음과 같다.

1	2	1	3	3	2	4
000(0) 001(1)	001(1) 010(2)	011(3) 001(1)	010(2) 001(1)	011(3) 001(1)	010(2) 010(2)	000(0) 100(4)
001(1)	011(3)	010(2)	011(3)	010(2)	000(0)	100(4)

[연산 과정]

 

int[] arr = new int[]{1,2,1,3,3,2,4};
int result=0;
for(int i = 0 ; i < arr.length ; ++i) {
	result ^= arr[i];
}
System.out.println("result = " + result);

결과 값 : 4

하지만, 이 방법으로는 짝이 맞지 않는 숫자가 단 하나만 존재한다는 가정이 있기에 가능한 것이지, 2개 이상을 찾기 위해서는 사용이 불가능하다.

 

그래서 짝지 맞지 않는 정수를 찾기 위해 Set을 이용해서 중복값이 발견되면 지울 수 있도록 하였다.

 

int[] arr = new int[]{1,2,1,3,3,2,4,5};

Set<Integer> dup = new HashSet<>();
Set<Integer> noDup = new HashSet<>();
for (int i = 0 ; i < arr.length ; ++i) {
    if (dup.contains(arr[i])) {
        noDup.remove(arr[i]);
    } else {
        noDup.add(arr[i]);
    }
    dup.add(arr[i]);
}
System.out.println("noDup = " + noDup);

결과 값 : [4, 5]