136. Single Number

source. https://leetcode.com/problems/single-number/

1. 요약 및 풀이방법

int를 element로 갖는 list가 들어온다.
이 list의 모든 element는 두번 존재한다.(단 한개를 제외하고)
이때, 한번만 존재하는 element를 찾는 문제이다.

조건 - linear runtime complexity

예시

ex-1
Input : nums = [2, 2, 1]
Output : 1

ex-2
Input : nums = [4, 2, 1, 2, 1]
OutPput : 4

ex-3
Input : nums = [1]
Output : 1

풀이방법

xor연산을 사용했다.
xor연산의 특징은 다음과 같다.

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0
,
a ^ 0 = a

또한, xor은 교환법칙이 가능하다.
즉, a ^ b = b ^ a 이다.

위 두 특징을 이용하여, nums list의 모든 element를 누적해서 xor연산을 거치면,
마지막 남은 수가 한번만 존재하는 수이다.

[4, 2, 1, 2, 1]
에서 교환법칙을 통해 정리하면

0 ^ 4 ^ 2 ^ 1 ^ 2 ^ 1 = 0 ^ 4 ^ 1 ^ 1 ^ 2 ^ 2
= 4

2. Code

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

3. 학습내용

처음에는 큰 list의 index를 이용하여 해결하려 했으나, 메모리낭비가 너무 심했다.
따라서 더 좋은 방법을 찾았고,
결과적으로 xor 비트연산을 이용하여 매우 간단하게 해결할 수 있었다.

4. 결과

(아래는 list를 미리 다 파놓고 index를 이용해서 구한 결과임. 속도와 메모리에서 차이가 남)