[Algorithm] 해커랭크 - Bit Manipulation: Lonely Integer

https://www.hackerrank.com/challenges/ctci-lonely-integer/problem

수열이 주어졌을 때 똑같은 값이 딱 하나인 녀석을 찾는 문제다.

아주 짧은 코드로 구현할 수 있었는데, 비트연산의 활용법을 잘 몰라서 약간 긴 코드가 되어버렸다

주어질 수 있는 수는 100 이하로 100개의 배열을 준비한 후 수열을 처음부터 탐색하면서 배열[수열의 값] 의 값을 1씩 증가시킨 후, 배열의 값이 1인 index를 리턴하는 방식으로 구현했다.

int lonely_integer(vector < int > a) {
    int numLength = 100;
    int isPair[numLength] = {};
    for (int i = 0; i < a.size(); i++)
    {
        isPair[a[i]] = isPair[a[i]] + 1;
    }
    for (int i = 0; i < numLength; i++)
    {
        if(isPair[i]==1)
            return i;
    }
    return -1;
}

근데 비트연산자를 이용하면 아주 간단하게 구현할 수 있다.

int lonely_integer(vector < int > a) {
    int r = 0;
    for(int i = 0; i < a.size(); i++)
    {
        r ^= a[i];
    }
    return r;
}

두번 나온다는 건, xor 연산을 두번하면 해당 비트는 모두 0이된다.

그럼 단 하나뿐인 값의 bit가 1이 되므로, 굳이 다시 검사할 필요 없이 값을 리턴하면 된다.

* 풀이시간 : 8분

* 풀이 중 문제점 : 처음 코드를 구현 할 때 numLength를 벡터 사이즈의 반으로 지정하는 실수를 범했다. (벡터 사이즈의 반만큼 숫자가 분포하니까 되겠지~ 하고 생각했던 게 잘못)