[리트코드] Single Number(python)

리트코드, Single Number_하나의 수(python)

Single Number - LeetCode

TL;DR

• 비트연산자(Bitwise operator)

문제 요약

1. 하나의 수를 제외하고 두 개의 숫자들이 존재하는 nums에 대해서 단일한 숫자를 반환하는 함수를 작성하라.
2. 선형 시간 복잡도와 변수 하나의 공간 복잡도 내에 문제를 해결해야 한다.

 

- 숫자가 원소로 있는 비어 있지 않은 리스트 nums에서 오직 하나만 있는 숫자를 반환하는 프로그램을 작성해야 한다.

- 선형 시간 복잡도라 하였기 때문에 반복문을 두 번 쓰거나 해서는 안 된다.

입출력 형태

입출력 예시

풀이

리스트를 한 번 순회하는 동안 답을 알아내야 하고, 별도의 비교를 위한 공간을 할당할 수도 없다. 이 때, 쓸 수 있는 좋은 방법 중 하나는 비트연산자를 사용해서 문제를 푸는 것이다.

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

 

비트 연산자 ^는 XOR(베타적 논리합) 연산을 수행한다. XOR 연산의 특징 중 하나는 같은 값끼리 연산을 진행했을 때는 0을, 서로 다른 값끼리 연산을 진행했을 때는 1을 결과로 낸다는 것이다.

0에 nums에 있는 숫자들을 XOR하게 되면 동일한 숫자를 만났을 때는 해당 숫자들이 연산 결과 제거가 되고 최종적으로는 하나만 남은 숫자가 남게 된다.

- 이를 통해 리스트를 선형 시간 복잡도 내 순회하면서 한 개의 변수(answer) 할당으로 문제를 해결할 수 있다.