[LeetCode] 338. Counting Bits (C++)

문제

 

https://leetcode.com/problems/counting-bits/

Counting Bits - LeetCode

 

풀이

 

난이도: Easy

 

 

위의 그림을 보면 알겠지만 

2^k ~ 2^(k+1) -1 의 수들은 k+1 번째 비트가 1이고 나머지는 0 ~  2^k -1와 뒷부분이 완전히 동일하다.

따라서 0 ~  2^k -1의 비트에서 1의 수들에 + 1을 붙인 것이 2^k ~ 2^(k+1) -1의 1의 개수가 된다.

따라서 계산해 둔 수들을 이용하면 선형 탐색으로 O(n)의 시간복잡도에 답을 구할 수 있다.

 

 

비트 연산에 중점을 두어 푼다면 다음과 같이 >>연산자로 더 깔끔히 구현이 가능하다.

vector<int> countBits(int num) {
     vector<int> res(num + 1, 0);
     for (int i = 1; i <= num; ++i) {
         res[i] = res[i >> 1] + (i & 1);
     }
     return res;
}

코드 출처: Four lines, C++, time O(n), space O(n)

 

코드

	class Solution {
	public:
	vector<int> countBits(int n) {
	vector<int> dp(n+1);
	dp[0] = 0;
	//복사할 배열의 길이
	int copy_len = 1, next_idx;
	for (; copy_len <= n; copy_len *= 2) {
	for (int idx = 0; idx < copy_len ; ++idx ) {
	next_idx = idx + copy_len;
	if (next_idx > n)
	break;
	dp[idx + copy_len] = 1 + dp[idx];
	}
	}
	return dp;
	}
	};

view raw Counting Bits.cpp hosted with ❤ by GitHub