70. Single Number

🎯 leetcode - 136. Single Number

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 70번 문제
- 비트 조작에 관련된 문제이다.

📌 날짜

2020.03.05

📌 시도 횟수

2 try

💡 Code

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

💡 문제 해결 방법

- 이번 장은 '비트 조작'에 관한 것이었다.
- 그래서 자연스럽게 비트로 푸는 방법을 고려해서 풀게 되었다.

- XOR은 '두 값의 각 자릿수를 비교해, 값이 같으면 0, 다르면 1을 계산'하는 연산이다.
- 따라서 이 XOR의 특성을 십진수에 적용해서 풀면 된다!
> 모든 nums의 요소들을 다 차례대로 XOR 연산을 누적해서 처리하면
> 값이 짝수개인 요소들을 XOR 연산으로 처리하면 `num ^ num = 0` 0이 된다.
> 반면 값이 1개만 존재하는 요소는 결국 연산이 다 끝난 후 혼자 남게 된다.

- 예시로 [2, 1, 1, 13, 2]의 모든 값을 XOR으로 누적해서 처리해보자.
----------------------------------
num: 2 / XOR result: 2
num: 2 / XOR result: 0
num: 1 / XOR result: 1
------- 2진수로 출력해본 결과 -------
num: 0b10 / XOR result: 0b10
num: 0b10 / XOR result: 0b0
num: 0b1  / XOR result: 0b1
----------------------------------
> 따라서 특정 값이 짝수개만큼 나오면 0으로 상쇄되고, 홀수 개 등장한 값만 남게 됨을 알 수 있다.

💡 새롭게 알게 된 점

- XOR을 특성을 이해하게 되었다.

❌ (한번에 맞추지 못한 경우) 오답의 원인