[파이썬/Python] Leet Code 338(Easy): Counting Bits

숨·2025년 9월 1일

코테

알고리즘 문제 풀이

목록 보기

125/128

📌 문제 : Leet Code 338

📌 문제 탐색하기

n : 입력되는 정수 ( $0 ≤ n ≤ 10^5$ )

문제 풀이

입력되는 정수 n에 따라 n+1 크기의 배열 arr을 반환하는 문제이다.

arr은 0부터 n에 해당하는 각 요소 i를 이진수로 나타냈을 때 1의 개수를 저장한 배열이다.
이를 구하기 위해선 arr을 만들고 각 요소들을 이진수 변환해준 후 1의 개수만 세어서 저장하면 된다.

가능한 시간복잡도

for문 → $O(n)$
이진수 변환 → $O(logn)$
count함수로 1의 개수 찾기 → $O(logn)$

최종 시간복잡도
최악의 경우 $O(nlogn) = O(10^5 * log(10^5))$ 이므로 충분히 동작할 수 있다.

알고리즘 선택

for문으로 접근해 계산

📌 코드 설계하기

1의 개수 저장할 리스트 정의
0부터 n까지 담고 있는 리스트 정의
배열에 접근해 이진수 변환 후 1의 개수 찾기

📌 시도 회차 수정 사항

📌 정답 코드

class Solution:
    def countBits(self, n: int) -> List[int]:
        # 1의 개수 저장할 리스트 정의
        ans = []

        # 0부터 n까지를 담고 있는 리스트 정의
        n_list = [i for i in range(n+1)]

        # 배열에 접근해 이진수 변환 후 1의 개수 세기
        for n in n_list:
            n_bi = bin(n)
            ans.append(n_bi.count('1'))
        
        return ans

결과

👍 다른 풀이

class Solution:
    def countBits(self, n: int) -> List[int]:
    	# 2의 거듭제곱 숫자 의미
        offset = 1
        
        # 0부터 n까지 1의 개수 저장할 리스트 초기화
        dp = [0] * (n + 1)
		
        # 1부터 n까지 반복해 1의 개수 계산
        for i in range(1, n+1):
        	# i가 다음 2의 거듭제곱 수가 되면 Offset을 i로 업데이트
            if offset * 2 == i:
                offset = i
            
            # dp[i]는 offset보다 큰 숫자의 1의 개수는 offset을 뺀 수의 1의 개수 + 1
            # (예: 6 (110 in binary) -> offset=4, 6-4=2, dp[2]=1, 따라서 dp[6]=1+1=2)
            dp[i] =  1 + dp[i-offset]
        
        return dp

Runtime : 1ms
DP를 활용해 중복 계산을 줄이는 방식이다. 2의 거듭제곱을 offset으로 활용하여 미리 1의 개수들을 구해놓는다. 미리 계산한 결과들을 계속 활용함으로써 계산량을 줄일 수 있다.
시간복잡도 $O(n)$ 으로 정답 풀이보다 더 효율적인 방법이다.