[Codility] Lesson 2.2 - OddOccurrencesInArray

N개의 정수로 이루어진 비어있지 않은 배열 A가 있다. 배열에는 홀수개의 요소가 있고 배열의 각 요소는 짝이 없는 하나만 빼고 같은 값의 다른 요소와 짝지을 수 있다.
예를 들어 배열 A가 아래와 같을 때

{9, 3, 9, 3, 9, 7, 9}

- 인덱스 0, 2의 값은 9로 동일
- 인덱스 1, 3의 값은 3으로 동일
- 인덱스 4, 6의 값은 9로 동일
- 인덱스 5의 값은 7로 짝이 없음

첫번째 풀이

• array를 set으로 만들어서 set에 array의 요소가 2개 미만으로 있는 것을 찾아서 반환하도록 해봤다.

public int solution(int[] A) {
    Set<Integer> aSet = Arrays.stream(A).boxed().collect(Collectors.toSet());
    List<Integer> aList = Arrays.stream(A).boxed().collect(Collectors.toList());

    int result = 0;
    for (Integer i : aSet) {
        if (Collections.frequency(aList, i) < 2) {
            result = i;
        }
    }

    return result;
}

• 결과는 실패. 엣지 케이스 하나에서 오답이 나왔고 performance test에서 모두 실패했다.
• 다시 생각해 보니 Set을 하나 만들고 인수로 넘어온 배열을 순환하면서 Set에 해당 요소가 있으면 지우고 없으면 추가하는 식으로 하면 Set에 하나만 남을 것 같아서 다시 시도

두번째 풀이

public int solution(int[] A) {
    Set<Integer> tempSet = new HashSet<>();

    for (int i : A) {
        if (tempSet.contains(i)) {
            tempSet.remove(i);
        } else {
            tempSet.add(i);
        }
    }
    return tempSet.iterator().next();
}

• 성공

이후에 찾아보니 XOR 연산으로 푸는 방법도 있던데...코드는 아래와 같다.

public int solution(int[] A) {
    int result = 0;

    for (int i : A) {
        result ^= i;
    }
    return result;
}

XOR 연산은 코드만 보고 바로 이해가 안가서 출력해 봤다.

0000(0) XOR 1001(9) = 1001(9)
1001(9) XOR 0011(3) = 1010(10)
1010(10) XOR 1001(9) = 0011(3)
0011(3) XOR 0011(3) = 0000(0)
0000(0) XOR 1001(9) = 1001(9)
1001(9) XOR 0111(7) = 1110(14)
1110(14) XOR 1001(9) = 0111(7)

비트의 값이 같으면 0이고 다르면 1이 된다.
첫번째 비교할 수 result를 0으로 하고 배열의 첫번째 요소부터 비교하면서 XOR 연산의 결과와 다음 요소와 XOR 연산을 계속 하면 같은 수들은 제거되어 0이 되고 외톨이인 수만 남게 된다.