[파이썬 알고리즘 인터뷰][비트연산] 싱글 넘버

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

단 하나의 수를 제외하고 모든 숫자가 2번씩 나올 때, 하나의 숫자 찾기

시간 복잡도는 linear, 공간 복잡도는 상수로 해결하기

 

책에서 구현된 코드

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

 

기억해야할 기법

• XOR를 이용한 중복 확인
  
  • 0과 XOR -> 숫자가 가진 특정 비트의 1만 1로 표시 = 자신과 같은 값
  • 같은 값과 XOR -> 모든 비트가 같으므로 0
  • 2번씩 등장하는 값들을 임의의 순서로 0과 XOR
    - 각 비트마다 1이 짝수번 등장 = 0으로 돌아옴

 

내가 구현한 코드

None

• 비트 연산을 수없이 봐왔는데 부끄럽게도 응용을 제대로 못했던 것 같다
• 이런 방식으로 응용한 게 너무 신기하다