(leetcode 문제 풀이) Single Number

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.
 
Example 1:
Input: nums = [2,2,1]
Output: 1

Example 2:
Input: nums = [4,1,2,1,2]
Output: 4

Example 3:
Input: nums = [1]
Output: 1
 
Constraints:
1. 1 <= nums.length <= 3 * 10^4
2. -3 * 10^4 <= nums[i] <= 3 * 10^4
3. Each element in the array appears twice except for one element which appears only once.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        counter = {}
        for num in nums:
            if num in counter.keys():
                counter[num] = 2
            else:
                counter[num] = 1
        
        for key, value in counter.items():
            if value == 1:
                return key

linear runtime complexity와 only constant extra space 라는 문제 조건을 보고 해시 자료구조(=파이썬 딕셔너리)를 써야겠다고 생각이 들었다. 물론, 이런 와중에도 더 좋은 해결 방법이 분명 있을 것이라고 확신했지만 나에겐 떠오르지 않았다.

LeetCode Discuss 섹션을 보니 아래와 같은 엄청난 코드가 있었다. 파이썬의 "^" 기호는 XOR 연산을 가리킨다.

# 모범 코드
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        answer = 0
        for num in nums:
            answer = answer ^ num
        return answer

다른 블로그 글을 보니 "XOR 연산을 활용하면 된다"고만 하고 별 다른 설명이 없어서 아쉬웠다. 이참에 복습할 겸 더 자세한 설명을 원하는 분들을 위해 정리해보았다. 예를 들어, a = 60, b = 13이라고 해보자.

a = 0011 1100
b = 0000 1101

연산자	기능	예시
&	AND연산	(a & b): 12 <- 0000 1100
|	OR연산	(a | b): 61 -> 0011 1101
^	XOR연산	(a ^ b): 49 -> 0011 0001
~	보수 연산	(~a): -61 -> 1100 0011
<<	왼쪽 시프트 연산자. 변수 값을 왼쪽으로 지정된 비트 수 만큼 이동	a << 2: 240 -> 1111 0000
>>	오른쪽 시프트 연산자. 변수 값을 오른쪽으로 지정된 비트 수 만큼 이동	a >> 2: 15 -> 0000 1111

이런 로직으로 보면 사실상 XOR 연산은 더하고 빼는 연산과 같다. 서로 비트부호가 다를 때만 참, 즉 1이 되기 때문인데 아래 예시를 보면 직관적으로 이해가 된다.

nums = [4, 1, 2, 1, 2]
a = 0
for i in nums:
  a = a ^ i
  print(a)

서로 다른 비트부호일 때 1이 된다는 것은 서로 같은 비트부호가 되면 0이 된다는 말이다. 위의 예시에서 4 -> 1 -> 2 까지는 서로 다른 숫자라 비트부호가 1이 되었지만, 이후 1 -> 2 가 반복되면서 비트부호상에선 0으로 상쇄되는 것이다.

이번 개념을 제대로 받아들이기 손으로 직접 비트부호를 표시해가며 푸는 것이 좋다.