LeetCode 136(Single Number, Python)

1. 문제 링크

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

Single Number - LeetCode

 

2. 문제 설명

• 정수로 구성된 nums가 주어졌을 때, 한 element만을 제외하곤, 모든 element가 2번 등장한다고 할 때,
  • 한번만 등장한 element를 반환
• 제한 조건
  • linear runtime complexity, 상수 extra space만 사용할 것
• 예시1) nums = [2,2,1] 이면 1만 1번 등장했으므로 1을 반환
• 예시2) nums = [4,1,2,1,2] 이면 4만 1번 등장했으므로 4를 반환

3. 기존 풀이

• history라는 dictionary를 만들고
  • history에 element 별 count를 담은 dict을 구성한 뒤,
  • dict의 value가 1일 때의 key값을 반환

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        history = {}

        for i in nums:
            if i not in history:
                history[i] = 1
            else:
                history[i] +=1 

        for i in history:
            if history[i] == 1:
                return i

 

4. 다른 풀이

• XOR 연산자 ^
• 2진수로 바꾸어 연산하는데 0과 1이면 1이 반환되고, 그 외(0과 0, 1과1)는 0을 반환
  • 예를 들어, 2^3의 경우 이진수로 10과 11을 연산하여 같은 위치에 1과 1이 있으면 0, 9과 1이 있으면 1이기 때문에 01로 반환되고 십진법으로 하면 1
  • 따라서 같은 수가 두번 연산되면 x^x =0이므로 상쇄효과가 존재
  • 그리고 이 연산은 교환 법칙이 성립하기에 연산 순서와 상관없이 2번씩 있는 수는 상쇄되어 사라지고 1번 있는 수만 남음

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

 

5. 배운점

• XOR 연산자