[Leetcode,c++] Single Number

문제

Single Number - LeetCode

 

코드

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int,int>m;
        int ans;
        
        for(int i:nums) m[i]++;
        for(auto it = m.begin(); it!=m.end(); it++){
            if(it->second==1){
                ans=it->first;
                break;
            } 
        }
        return ans;
    }
};

 

풀이

단순히 배열에서 중복되지 않은 단 하나의 수를 찾아서 출력하는 문제였습니다. 나름 위 풀이처럼 풀었을 때 O(n)이기에 효율적인 코드라고 생각하고 제출했으나, 시간이 꽤 걸린 것을 알 수 있습니다. 그렇게 다른 사람의 풀이를 보다가 아래와 같은 풀이를 보았습니다.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        
        for(int i:nums) ans^=i;
        return ans;
    }
};

이전에 map을 사용하여 풀었던 풀이보다 시간이 두배나 적게 걸렸고, 메모리도 훨씬 덜 잡아먹은 것을 볼 수 있습니다.

풀이를 보면 논리연산자를 이용해서 푼 풀이인데 그 방법이 신박했습니다. XOR 연산인 ^ 비트연산자는 아래와 같은 진리표를 나타냅니다.

INPUT		OUTPUT
A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

 

이 원리를 이용해서 배열에 값이 [4,1,2,1,2]가 있다고 생각하고 ans^=arr [i]; 구문을 수행한다고 해봅시다.

처음 ans = 4가됩니다.

그다음은 0100^0001 = 0101 이 되어 ans = 5이 되고,

다음, 0101 ^ 0010 = 0111, ans=7,  

다음, 0111 ^ 0001 = 0110, ans= 6,

다음, 0110 ^0010 = 0100 , ans=4 가 되어 중복되지 않은 4의 값을 뽑아내는 것을 알 수 있습니다.

결국 똑같은 값에 대해 ^ 연산을 두 번 수행하게 되면, 원래의 값으로 돌아오는 원리를 이용한 것입니다.