문제 링크

나의 논리

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        
        nums.sort()
        xor = 0
        
        for i in range(len(nums)):
            
            if xor == 0:
                xor = nums[i]
            else:
                if xor ^ nums[i] == 0:
                    xor = 0
                else:
                    break
                    
        return xor

문제에서 동일한 수는 2번 반복된다고 했으므로 리스트를 정렬해서
인접 한 수 끼리 xor연산을 한다. 인접한 두 수가 동일한 수라면 xor을 했을때 0이고 , xor했을때 0이 아니라면 인접 한 두수가 다르므로 둘 중 하나를 리턴한다.

둘 중 하나를 고르는건 일정한 규칙에 의해서 고른다.
규칙은 다음과 같다.
우선 xor은 0으로 초기화를 하고 리스트의 첫번째 원소와 비교한다.
xor이 0일때는 현재 원소는 리스트의 인접한 두 수 중 첫번째 수라는 의미이다. xor에 첫번째 수 넣고, 두 수 중 2번째 수로 넘어간다.
두 수 중 두번째 수를 만났을때는 실질적으로 첫번째 수, 두번째수를 xor 연산하게 되는 셈이다. 이때 0이라면 두수는 같다. 다르다면 xor에 대입된 수가 정답이 된다.

정답 논리

정답은 훠얼씬 간단한 논리이다.

앞에서 부터 비트를 누적하는 방식이다. 같은 수는 두개뿐이라서 앞에서 누적되더라도 뒤에서 언젠간 xor 연산에 의해 0으로 바뀐다. 이런걸 반복하다보면 결국엔 남는건 단 하나 있는 수 밖에 없게된다.

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