codility lesson 02 OddOccurrencesInArray

문제

A non-empty array A consisting of N integers is given. The array contains an odd number of elements,

and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the elements at indexes 0 and 2 have value 9,
the elements at indexes 1 and 3 have value 3,
the elements at indexes 4 and 6 have value 9,
the element at index 5 has value 7 and is unpaired.
Write a function:

function solution(A);

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9
A[3] = 3 A[4] = 9 A[5] = 7
A[6] = 9
the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

N is an odd integer within the range [1..1,000,000];
each element of array A is an integer within the range [1..1,000,000,000];
all but one of the values in A occur an even number of times.

문제해설 : 비어있지 않은 배열 A는 integers N으로 구성되어 있습니다.

배열은 홀수 개의 요소가 포함되어 있으며, 각 요소는 한개의 요소를 제외하고, 다른 요소와 같은 값으로서 쌍을 이룰 수 있습니다.

예를 들어 배열 A는 다음과 같습니다.

A[0] = 9
A[1] = 3
A[2] = 9
A[3] = 3
A[4] = 9
A[5] = 7
A[6] = 9

인덱스 0과 2의 값은 3 입니다.
인덱스 4와 6의 값은 9 입니다.
인덱스 5의 값은 7이며 쌍을 이루지 않습니다.

다음 solution(A) 함수를 작성하세요.

위 조건을 만족하는 N integers로 구성된 배열 A는 쌍을 이루지 않는 값을 리턴합니다.

예를 들면 주어진 배열 A는

A[0] = 9
A[1] = 3
A[2] = 9
A[3] = 3
A[4] = 9
A[5] = 7
A[6] = 9

위 설명대로라면 7을 리턴합니다.

다음 가정을 토대로 효율적인 알고리즘을 작성하세요.

N은 [1…1,000,000]의 범위를 가진 홀수 입니다.
배열 A의 각 요소는 [1..1,000,000,000]의 범위를 가집니다.
A의 값 중 하나를 제외하고 모두 짝수 번 발생합니다.

답안 해설

내가 작성한 코드 :

function solution(A) {
    var arr = [];

    for(var i=0; i < A.length; i++) {
        var foundVal = arr.find(item => {
            return item.value === A[i];
        });

        if(foundVal == undefined) {
            arr.push({
                value: A[i],
                count: 1
            });
        } else {
            foundVal.count++;
        }
    }

    var result = arr.find(item => {
        return item.count % 2 !== 0
    });

    return result.value;
}

내가 생각한 접근법은 배열을 새로 만들고 각 배열의 요소에 대한 count를 저장한다.
배열 A를 순회하면서 중복되는 값의 count는 증가할 것이고 배열 A를 전부 순회하였을 때, 2로 나눠지지 않는 값을 찾는다.
시간 복잡도는 배열 A를 순회하면서 이에 매칭되는 값을 저장하는 arr도 순회해야 하기 때문에 O(N^2)가 된다.

P.S 상당히 고민 끝에 푼 테스트였는데 결과도 좋지 않아 현타가 왔다.

Test Score는 66%였으며 Performance tests에서 medium, big1, big2에서 Timeout error가 났다.

도대체 어떻게 효율적으로 짤 수 있을까 생각하다 결국엔 답을 찾아보았다.
답을 찾아보고 난후 더욱 맨붕이 심하게 왔다…
봐도 이해가 가지 않았기 때문…

이 문제에 대한 최적의 알고리즘은 다음과 같다.

function solution(A) {
    var result = 0;

    for(var item of A) {
        result ^= item;
    }

    return result;
}

(코드가 어찌 이리 간단하면서도 이해가 가지 않을 수가 있지??!?)
(저기서 XOR연산을 왜 하는거지??)
결론은 간단했다. XOR (배타적 논리합: XOR연산은 두 개의 비트 값이 다르면 1, 같으면 0을 돌려준다) 연산의 특성 때문에 자체적으로 쌍을 이루지 않는 값은 필터링이 된다.
XOR연산은 다음과 같은 특성을 가진다.

X^0 = X
X ^ X = 0

즉 같은 값을 XOR연산을 한다면 그 값은 0이 되며 0과 X의 XOR 연산은 자기 자신이 된다.

예를 들어 3^0의 경우

0000
0011
----
0011

본인과 같은 3이 되고,

0011
0011
----
0000

둘다 같은 비트이기 때문에 0이 된다.

즉 위 문제의 배열 A에서 1개의 요소만 쌍을 이루지 않고 나머지는 모두 같은 값이므로

A[0]^A[1]^A[2]….A[N-1]^A[N] 이 되며
쌍을 이루는 값들은 XOR연산에 의해 0으로,
쌍을 이루지 못한 요소는 그대로 남게되어
0^A[X] = A[X] 가 된다.
결국 쌍을 이루지 못한 값만 남게 되는것이다.

출처 : Solution to Odd-Occurrences-In-Array by codility

codility lesson 02 OddOccurrencesInArray

문제

답안 해설

gamjamanduu