[Leetcode/C++] 136_Single Number

문제는 다음과 같습니다.

이번주 스터디 관련 문제는 "비트 조작"에 대한 문제입니다.
비트.. c언어 배울때 윤성우 열혈에서 잠깐 보았던 것 같은데 그 외에 따로 본 적이.. 음 어셈블리언어에서 명령어가 4byte.. 그 외에는 직접 쓴 적이 없는 것 같아요.

생각보다 이 주제에 대해서 많이 생소한 것 같습니다.

제가 먼저 푼 방법은 시간복잡도 nlogn 풀이입니다.
풀이는 다음과 같습니다.

• 먼저, sort를 이용해 입력받은 벡터를 정렬합니다.
• 인접한 두 항이 다른 경우가 single number인 경우이므로, 값을 반환하고 함수를 종료합니다.

코드는 다음과 같습니다.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if(nums.size()==1) return nums[0]; // 원소가 1개인 경우 예외처리
        
        int res=0;
        
        sort(nums.begin(), nums.end());
        
        for(int i=0; i<nums.size(); i+=2){
            if(nums[i]!=nums[i+1]){
                res=nums[i];
                break;
            }
        }
        return res;
    }
};

다음 풀이는 비트 연산자를 이용한 풀이입니다.
먼저 저는 XOR 연산자인 ^를 이용하였습니다.
이유는 다음과 같습니다.
먼저 동일한 두 수에 대하여 XOR연산을 취하면, (XOR는 두 값이 달라야 1을 반환하고 같으면 0을 반환하므로) 0을 반환할 것입니다.
즉, 같은 수가 있다면 0을 반환하므로 상쇄되는 것과 마찬가지라고 볼 수 있습니다.
반면, 같은 수가 없는 경우, 그대로 그 수가 남아있을 것입니다.

따라서 res=0으로 초기화 한 이후,
벡터의 모든 값과 res를 ^ 연산을 한 후, 다시 그 결과값을 res에 담으면,
결국 짝이 없는 수만 남게 될 것입니다.

제 코드는 다음과 같습니다.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res=0;
        
        for(int i=0; i<nums.size(); i++){
            res = res^nums[i];
        }
        return res;
    }
};