(Leetcode) 191 - Number of 1 Bits
New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time
위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.
https://leetcode.com/problems/number-of-1-bits/description/
이번 문제는 binary문제이다. bit 연산자를 이용해서 풀면 된다.
쉽게 접근하기
class Solution:
def hammingWeight(self, n: int) -> int:
mask = 0xFFFFFFFF
bits = list("{0:b}".format(n & mask))
return len(list(filter(lambda b: b == "1", bits)))
제대로 접근하기
class Solution:
def hammingWeight(self, n: int) -> int:
res = 0
while n:
res += n%2
n = n>>1
return res
2진수의 마지막 부분은 1을 나타낸다. 따라서 맨 마지막 숫자가 1일 경우 n%2는 1이 된다. 반대로 0일 경우 n%2는 0이 된다.
>> 연산자는 우측에 있는 숫자만큼 비트를 옮긴다. n>>1 는 1bit 만큼 옮긴다. 옮기면 사라진다. n이 만약 1000 이라면 100 이 되는 것이다.
더 야매로 접근하기
파이썬만 되는 방법
class Solution:
def hammingWeight(self, n: int) -> int:
return bin(n).count('1')
참고
지난번 binary문제에서도 이야기 했지만 bit 연산자에 대한 설명은 FAQ: What do the operators <<, >>, &, |, ~, and ^ do?를 참고하면 좋을 것 같다.
자바로 다시 풀기 (24.05.25)
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count += n % 2;
n = n >> 1;
}
return count;
}
TC, SC
시간 복잡도는 O(logn)이고, 공간 복잡도는 O(1)이다. logn 인 이유는 bit의 수는 log에 따르기 때문이다.