[codility] OddOccurrencesInArray

배열 내의 같은 값을 원소 중에서 짝을 이루지 못하는 원소의 값을 반환하는 문제.

등장한 값들의 개수를 카운트하여 개수가 홀수인 것을 찾아내는 방식으로 해결했다.

원소값의 범위가 $0$~$10^9$이기 때문에 배열을 사용하면 메모리 초과가 발생하므로 map을 사용했다.

마지막 테스트케이스에서 주어진 배열 A의 크기가 $10^6$이었고 제한시간이 0.3초였지만 실행결과 0.6초 정도가 걸려서 TLE에 걸렸다. set내에 값이 없으면 insert하고 이미 있으면 erase해주는 방식을 써서 시간을 더 줄여봤지만 결과는 0.5초로 여전히 TLE였다.

$O(N*NlogN)$보다 더 나은 방법이 도저히 생각나지 않아 다른분들의 풀이를 찾아보았다.

해답은 XOR연산이었는데 같은 값을 두 번 XOR연산하면 XOR연산을 하지 않은 것과 같은 결과가 나오므로 $O(N)$으로 해결이 가능하다.

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

cpp code

#include <map>

int solution(vector<int> &A) {
    map<int, int> M;
    for (int i : A) M[i]++;
    for (auto p : M) {
        if (p.second & 1) return p.first;
    }
}