[LeetCode]Single Number

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

Single Number - LeetCode

 

문제 분석

주어진 nums 리스트에서 한번만 등장하는 숫자를 찾는 문제입니다.

 

처음 시도한 답안

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        count_dict = {}
        
        for num in nums:
            if num in count_dict:
                count_dict[num] += 1
            else:
                count_dict[num] = 1

        count_dict = sorted(count_dict.items(), key=lambda x: x[1])

        return list(count_dict)[0][0]

접근 방법

1. nums 배열을 순회하면서 count_dict에 등장한 숫자에 대한 카운트를 누적합니다.
2. count_dict를 value 기준으로 정렬하면 한번만 등장한 숫자를 구할 수 있습니다.

가장 단순한 방법으로 리스트를 순회해서 등장한 숫자의 카운트를 셉니다. 다만, 배열이 커지면 커질수록 오래 걸린다는 단점이 있습니다.

 

두번째로 시도한 답안 

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ## RC ##
        ## APPROACH : XOR ##
        
        ## TIME COMPLEXITY : O(N) ##
        ## SPACE COMPLEXITY : O(1) ##
        
        # XOR 연산의 특징 : 같은 값끼리 연산하면 걍 0이 되어버림.
        # 따라서 2개 쌍의 경우 모두 0이 되고 혼자 남은 숫자만 남아버림.
        # 0 XOR 99 = 99

        # If we take XOR of zero and some bit, it will return that bit
        # a XOR 0 = a, a XOR 0=a
        # If we take XOR of two same bits, it will return 0
        # a XOR a = 0 a XOR a=0
        # a XOR b XOR a = (a XOR a) XOR b = 0 XOR b = b 
        # a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
        # So we can XOR all bits together to find the unique number.
        
        a = 0
        for i in nums:
            a ^= i
        return a

접근 방법

1. XOR 연산을 통해서 한번만 등장하는 숫자를 구할 수 있습니다.

굉장히 놀라운 솔루션을 발견하게 되어서 가져왔습니다. XOR 연산을 이용하는 것입니다.

XOR 연산의 특징은 같은 값끼리 연산하면 결과값이 0이 되어버립니다. 따라서 리스트를 반복하면서 XOR 연산을 한다면, 2개의 쌍이 존재하는 숫자들은 모두 0이 되어버리고 결과적으로 1개만 존재하는 숫자가 남게 됩니다.