99클럽 | 비기너
2️⃣ 338. Counting Bits
🏷 Topic : Dynamic Programming Bit Manipulation
Easy
Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Example 1:
Input: n = 2
Output: [0,1,1]
Explanation:
0 --> 0
1 --> 1
2 --> 10
Example 2:
Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101
Constraints:
0 <= n <= 105
Follow up:
- It is very easy to come up with a solution with a runtime of
O(n log n). Can you do it in linear timeO(n)and possibly in a single pass? - Can you do it without using any built-in function (i.e., like
__builtin_popcountin C++)?
Accepted 1.1M | Submissions 1.4M | Acceptance Rate 78.4%
✔ Solution with Loop (링크🔗)
class Solution {
public int[] countBits(int n) {
int[] answer = new int[n + 1];
int n2 = 1;
for (int i = 1; i <= n; i++) {
if (i == n2) {
answer[i] = 1;
n2 *= 2;
} else {
answer[i] = answer[i - n2 / 2] + 1;
}
}
return answer;
}
}채점 결과
✔ Solution with Loop and Arithmetic Operator
class Solution {
public int[] countBits(int n) {
int[] answer = new int[n + 1];
for (int i = 0; i <= n; i++) {
int n2 = i;
while(n2 != 0 ) {
if (n2 % 2 == 1) {
answer[i]++;
}
n2 /= 2;
}
}
return answer;
}
}채점 결과
💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍
처음에 문제를 2번째 풀이 방법으로 풀었는데 10ms가 나와서
더 빠른 코드를 써보고 싶어서 한참을 도전하다가 재귀함수 코드 쓰는 것은 포기하고😵
다른 코드로 시도하여 2ms가 걸리는 코드를 작성할 수 있었다.
- 매개변수로 정수
n이 주어진다. - 길이가
n + 1인 정수 배열ans를 만든다. ans의i번째 인덱스의 값은
10진수i를 이진법으로 표현했을 때, 그 이진법 표현에 들어 있는 `1의 개수이다.ans를 반환한다.
10진법 --> 2진법 : 1 개수
0 --> 0 : 0
1 --> 1 : 1
2 --> 10 : 1
3 --> 11 : 2
4 --> 100 : 1
5 --> 101 : 2
6 --> 110 : 2
7 --> 111 : 3
...
- $2^{n}$의
1의 개수는 무조건1 - 그 다음 오는 정수들은 0부터 $2^{n} - 1$까지의 수에 1을 더한 수가 순차적으로 온다.
이를 이용하여 반복문으로 ans의 각 요소에 값을 할당해 보자.
1. 반환할 정수형 배열 answer을 초기화 하자.
int[] answer = new int[n + 1];2. 반복문을 돌때, 인덱스가 2의 거듭제곱인지 아닌지 체크할 변수 n2를 1로 초기화
int n2 = 1;3. 배열의 1번째 인덱스부터 n번째 인덱스까지 반복문을 돌면서 값을 할당하자.
- 만약 인덱스
i가 2의 거듭제곱이면(i와n2가 같으면),answer의i번째 인덱스에1을 할당하고n2에 곱하기 2를 해 줌.
if (i == n2) {
answer[i] = 1;
n2 *= 2;
}i가 2의 거듭제곱이 아니면(i와n2가 다르면),answer의i번째 인덱스에answer의i - n2 / 2번째 인덱스의 값 + 1을 할당.
else {
answer[i] = answer[i - n2 / 2] + 1;
}4. answer을 반환
return answer;💬 무엇을 새롭게 알았는지
그래도 포기하지 않고 코드를 써서 8ms 더 빠른 코드를 작성할 수 있었다.
포기하지 않고 시도해 본 경험을 얻을 수 있었다.
📚 References(참고 자료)
🆙 Next Level
+ 69회 현충일 기념 66줄 코드 쓰기 문제 : 코딩테스트 연습 | 코딩 기초 트레이닝 | 날짜 비교하기
