LeetCode > 136. Single Number

문제 링크 : https://leetcode.com/problems/single-number/

처음에 일단 중복된 배열들을 제거.. 하거나.. 하튼 어떻게 처리해야겠다 라는 생각은 했는데..
아무리 생각해도 안떠오름..
그래서 discussion을 봤는데.. 비트 연산자..? 라는 것을 활용한 풀이를 보았다..
상상도 못한 풀이 ㄴㅇㄱ(근데 맨날 안풀려서 해결 방법 구글링해보면 이런 상태임..)

비트 연산자란?
: 비트 연산자 (Bitwise operator)는 2진수 문자열 피연산자에 대해 비트 단위의 연산 작업을 수행합니다.

파이썬 내장함수 bin()을 이용해서 10진수를 2진수로 변환하면

10진수 12는 1010 (2), 10진수 5는 2진수로 101 (2) 임을 알 수 있습니다.

a ^= b : a와 b의 비트를 XOR 연산한 후 결과를 a에 할당

^ 연산자

a ^ b result
1 ^ 1 1 `
1 ^ 0 0
0 ^ 1 0
0 ^ 0 0
^연산자는 XOR연산자 라고 하는데 두 수가 서로 다른 값을 가질 때, 1을 반환한다.

0b1100 ^ 0b1001 = 0b0101

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans =0 
        for i in nums:
            ans ^= i
        return ans
        

예를들어

singleNumbers2([1,2,3,4,3,2,1]):
= 1 ^ 2 ^ 3 ^ 4 ^ 3 ^ 2 ^ 1
= (1 ^ 1) ^ (2 ^ 2) ^ (3 ^ 3) ^ 4
= 0 ^ 0 ^ 0 ^ 4
= 4

이런 원리로.. 된다고 한다...

참고 : https://blog.naver.com/PostView.nhn?isHttpsRedirect=true&blogId=ericalee97&logNo=222244580163&categoryNo=0&parentCategoryNo=0&viewDate=¤tPage=1&postListTopCurrentPage=1&from=postView