70. Single Number

리트코드

• 딱 하나를 제외하고 모든 엘리먼트는 2개씩 있다. 1개인 엘리먼트를 찾아라.

1. XOR 풀이

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

• 단 1개의 엘리먼트를 찾는 데 적당한 연산자가 있다. 배타적(Exclusive) OR, XOR이다.

• XOR은 입력값이 서로 다르면 True, 서로 동일한 경우 False가 되는 논리 게이트 연산자이다.

• 두 번 등장한 엘리먼트는 0으로 초기화되고, 한 번만 등장하는 엘리먼트는 그 값을 온전히 보존한다.

  • 즉 배열의 모든 값을 XOR 하면, 단 한 번만 등장하는 엘리먼트만 그 값이 남게 된다.