[1스4코2파] #151. LeetCode pattern 136. Single Number

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (151일차)
[4코1파] 2023.01.13~ (142일차)
[1스4코1파] 2023.04.12~ (53일차)
[1스4코2파] 2023.05.03 ~ (32일차)

Today :

2023.06.03 [151일차]
LeetCode Patterns
136. Single Number
https://leetcode.com/problems/single-number/

136. Single Number

문제 설명

문제 풀이 방법

처음에는 counter를 써서 딕셔너리로 만들고 거기서 value 값이 1인 애를 뽑아왔지만?
linear runtime으로 풀어라! 라는 말이 있었기 때문에 틀린 풀이였던 것이다..

일단 다른 사람들이 푼 코드를 봤는데
math 잖아????????????????

비트연산으로 single Number 를 뽑아낼 수 있는데..
일단 조건이 nums 라는 배열을 가진 리스트 내에서
하나의 원소만 single 이고 나머지는 'twice' 두번 나올 수 있다는 가정하에서 비트연산을 할 경우
총 원소를 비트연산하면 single Number가 나온단다

놀라운 수학의 세계이시다 뭐고

내 코드

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

증빙

여담

비트연산이 버릇없이 툭 튀어나오다니