파이썬 ^= (Xor) 연산으로 짝수 지우기
파이썬 ^= (Xor) 연산으로 짝수 지우기 — #LeetCode #개발자의도구들 only 파이썬 목표 참고 : 여기 one-way search even check 이번에도 배열을 ...
#LeetCode#Naver Blog
#LeetCode #개발자의도구들
- only 파이썬
- 목표 참고 : 여기
one-way search even check
LeetCode(esay 136. Single number) 75.2%
이번에도 배열을 한번 탐색하여 홀수와 짝수를 찾아야한다. one-way search 전략과 동일하게 생각해보았다.
전략
⚠️ 시간/공간 복잡도의 제한사항 ; O(n)
1. arr을 만든다. 혹은 hash도 괜찮다?
2. one-way search를 진행한다.
3. nums를 순회한다
>>> num이 arr에 있다면 arr에서 num을 제거
>>> num이 arr에 없다면 arr에 push
4. 최종적으로 num에 남아있는 숫자가 정답
⌛ 시간 복잡도
arr에서 찾기 = O(n)
arr에서 제거 = O(n)
nums를 순회 = O(n)
3O(n) = O(n)
🛰️ 공간 복잡도
arr = O(n)
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
arr = []
for num in nums:
if num in arr:
arr.remove(num)
else:
arr.append(num)
return arr[0]
- 맞긴한데 30 빠른 코드가 있다.
- 추가 메모리가 소요되어서 별로다.
- 추가 메모리 소요 없이 해보자.
XOR 연산으로 30배 빠른 코드 작성하기
🤔 XOR 연산이란?
bit단위 연산으로 각 비트 자릿수를 XOR연산을 수행해줌
ex) 3 ^ 5 =
011
101
----
110 = 6
❓ 이게 여기서 왜 필요한가?
- 자기 자신과 xor연산을 수행하면 0이 된다.
- 그럼 xor연산으로 0이 안되는 경우 해당 값이 그대로 남아있을 것이다.
odd = 0
for num in nums:
odd ^= num
return odd