[Leetcode/파이썬] 136. Single Number

Single Number

---

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,1]

Output: 1

Example 2:

Input: nums = [4,1,2,1,2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once

 

'''
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        dct = defaultdict(list)
        for i in range(len(nums)) :
            dct[nums[i]].append(i)

        for key, val in dct.items() :
            if len(val) == 1 :
                return key
'''
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0

        for num in nums :
            res ^= num

        return res

시간복잡도를 선형 시간 복잡도, 상수의 추가 공간을 사용하라고 하는데 이게 무슨 의미인지 생각해보자. 잘 모르겠어서 챗GPT에 물어봐야 겠다

시간복잡도에 대해서는 알고 있었는데 ($O(N)$으로 해결하라) 상수의 추가 공간에 대해서 조금 애매해서 물어보았다. 쉽게 얘기해서 시간복잡도는 $O(N)$으로, 공간복잡도는 $O(1)$으로 해결하라는 의미이다. 

처음에는 일반적인 Counter 라이브러리나 이를 구현해서 해결하였는데, 생각해보니 이는 공간복잡도가 커지는 것 아닌가 생각이 든다. 딕셔너리를 만들고 그 안에 수를 채워넣으니까 말이다. 그렇다면 수를 계산할 수 밖에 없다는 의미이다. 

그래서 얻은 해답이 XOR 연산이다. 비트 연산으로 다르면 True, 같으면 False 를 하는 연산이다. 파이썬에서는 True 를 1, False 를 0으로도 표현되기 때문에 이를 활용한 풀이법이라 할 수 있다. 

첫번째 케이스를 예를 들어, 숫자 하나씩 불러와서 res의 변화를 보자. res = 2, 0, 1이 나타나게 되며 최종 res = 1 이 return 되게 된다. 

두번째 케이스에서는 res = 4, 5, 7, 6, 4 로 나타나게 되며, 최종 res = 4 가 되게 된다. 

비트로 바꿔서 계산해보면, [4, 1, 2, 1, 2] 는 [100, 001, 010, 001, 010] 이 되므로 res = 0b[100, 101, 111, 110, 100]으로 표현된다. 이걸 잘 생각해보면 풀 수 있는 문제이다. 

이런 문제를 잘 해결해보지 않아서 Counter 하는 방법으로 해결할 수도 있지만, 출제자가 원하는 대로도 풀어보았다.