[Codility] Lesson 2 : OddOccurrencesInArray (자바/JAVA)

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

OddOccurrencesInArray coding task - Learn to Code - Codility

배열 안에 있는 수 중, 짝이 없는 애만 찾아서 리턴하면 된다.

처음에 시도한 방법

class Solution {
    public int solution(int[] A) {
        int answer = 0;
 
        for(int i = 0; i < A.length; i++) {
            if(A[i] == 0) {
                continue;
            }
 
            for(int j = i+1; j < A.length; j++) {
                if(A[i] == A[j]) {
                    A[i] = 0;
                    A[j] = 0;
                    break;
                }
            }
            if(A[i] != 0) {
                answer = A[i];
            }
 
        return answer;
    }
}

이중 for문은 시간복잡도를 늘리는 가장 쉬운 방법이라고 생각해서 되도록 사용하지 않으려하는데...

알고리즘 문제를 풀다보면 이를 쓰도록 만드는 문제가 참 많은 것 같다.

이것도 역시 그런 미끼를 던졌고 난 물었다.

풀긴 풀었지만 효율성에서 점수가 깎여서 66%가 나오고 말았다.

찾아보니 많은 분들이 XOR 비트연산으로 해결한 것 같다.

XOR 연산은 1과 다른 수(1,0)면 1을 같은 수(1,1 / 0,0)면 0을 리턴하는데,
예를 들어, 1011 ^ 1010 = 0001이 된다.

처음엔 이 방법이 같은 수가 연속될 때만 0으로 리턴하는 줄 알았는데 상관없이 계속 XOR 연산을 해나가다보면

같은 수는 전부 0이 되고 짝이 없는 수만 그대로 리턴이 되는 것 같다.

(임의의 수로 테스트를 해보니깐 그렇게 되는데 알면서도 신기한 이 광경)

class Solution {
    public int solution(int[] A) {
        int answer = 0;
        for(int num : A) {
            answer ^= num;
        }
        return answer;
    }
}