LeetCode 191 - Number of 1 Bits

이 문제는 정수의 이진 표현에서 1이 몇 개인지 세는 문제다. 반복마다 마지막 비트를 확인하고, 그 비트를 처리한 뒤 수를 2로 나누는 흐름만 잡으면 된다.

문제 링크 & 설명

문제 링크: 191. Number of 1 Bits
요약: 정수 n이 주어졌을 때, 이진 표현에 포함된 1의 개수를 반환하는 문제다.

예를 들어 n = 11이면 이진수로 1011이고, 1은 세 개라서 결과는 3이다.

이 문제는 숫자를 문자열로 바꾸지 않아도 풀 수 있고, 현재 값의 가장 오른쪽 비트를 확인하면서 계속 2로 나누면 된다.

접근 방법

가장 먼저 떠올린 방식은 현재 수를 2로 나눈 나머지를 보는 것이다. 어떤 정수든 2로 나눈 나머지는 마지막 비트와 같고, 나머지가 1이면 1비트를 하나 센 것이고 0이면 그대로 지나가면 된다. 그다음에는 n을 2로 나눠서 한 자리씩 오른쪽으로 밀어내면 다음 반복에서 새로운 마지막 비트를 다시 볼 수 있다.

count = 0
while n > 0:
    count += n % 2
    n //= 2

이 방식의 장점은 이진수 전체를 따로 만들지 않아도 된다는 점이고, 숫자 자체를 계속 줄여 가면서 비트만 확인하면 되므로 로직도 직선적이다.

트러블 슈팅

이 문제에서 핵심은 반복 조건이다. n이 0이 될 때까지 계속 봐야 마지막 비트까지 빠짐없이 셀 수 있는데, 처음에는 n >= 2처럼 잡아도 돌아가는 것처럼 보일 수 있지만 그 경우 마지막 한 비트를 따로 처리하지 않으면 결과가 어긋난다. 그래서 이 문제는 n > 0 조건으로 끝까지 돌리는 편이 더 분명하고, 마지막 비트를 직접 더하는 방식이므로 카운트도 0에서 시작하는 편이 자연스럽다. 처음부터 1로 두고 시작하면 입력값에 따라 별도 보정이 필요해진다.

복잡도 분석

시간 복잡도: O(log n)
- n을 2로 나눌 때마다 값이 절반으로 줄어든다.
- 정수의 비트 수만큼만 반복하므로, 반복 횟수는 n의 이진 자릿수에 비례한다.
공간 복잡도: O(1)
- 비트 개수와 현재 수만 유지하면 된다.
- 별도의 배열이나 문자열을 만들지 않는다.

구현 코드

최종 코드는 2로 나눈 나머지와 정수 나눗셈을 사용해 1비트 개수를 센다.

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        while n > 0:
            count += n % 2
            n //= 2

        return count

이 풀이는 이진수 전체를 직접 만들지 않아도 되고, 매 단계에서 마지막 비트만 보면 되기 때문에 구현이 단순하다. 숫자를 반으로 줄여 가는 흐름만 기억하면 된다.

요약 및 회고

이 문제는 정수를 이진수로 바꿔서 마지막 비트를 반복적으로 확인하는 문제다. 코드를 길게 만들 필요도 없고 자료구조를 새로 쓸 필요도 없으며, n을 계속 2로 나누면서 남은 비트를 확인하는 방식만 잡아두면 같은 유형의 비트 문제도 비슷한 흐름으로 풀 수 있다.