.leetcode(338. Counting Bits)

문제

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

문제 풀기 전

1. 앞에 푼 데이터를 이용하면 되겠다라는 생각이 들었다.
   0이면 0
   1이면 1

   2이면 10 <<앞에 이미 구한 0에서 1만 추가됨
   3이면 11 <<앞에 이미 구한 1에서 1만 추가됨

   4이면 100 <<앞에서 이미 구한 0에서 1만 추가됨
   5이면 101 <<앞에서 이미 구한 1에서 1만 추가됨
   6이면 110 <<앞에서 이미 구한 2에서 1만 추가됨
   이런 규칙을 발견했다. 이걸 구현하기만 하면 되었다.

직접 푼 풀이

소요시간: 30분(21:09 ~ 21:39)

class Solution {
    public int[] countBits(int num) {
        if (num == 0) {
            return new int[]{0};
        }
        int[] box = new int[num+1];
        box[0] = 0;
        box[1] = 1;

        int len = 2;
        int index=1;
        while(true) {
            if (index == num) {
                break;
            }

            for(int i=0; i<len; i++) {
                if (index == num) {
                    break;
                }
                box[++index] = box[i]+1;
            }
            len = index+1;
        }

        return box;

    }
}

느낀점

1. 아이디어는 그래도 바로 생각났는데 구현이 생각보다 어려웠다. 한번 좀 익혀둘 필요가 있다.

2. 나는 bit 연산을 사용하지 않았지만, 실제로 비트 연산을 하면 더 쉽게 간단하게 나타낼 수 있다.

3. 그리고 내가 푼 방식은 dp + Most Significant Bit으로 이진법 맨 앞자리 수를 채워가는 것이었다면 반대로 뒤에를 하나씩 채워가는 DP + Least Significant Bit 방법도 있다.

   • 2: 10

   • 3: 11

   • 4: 100 << 2(10)에다가 뒤에 0을 붙이면 된다.

   • 5: 101 << 2(10)에다가 뒤에 1을 붙이면 된다.

   • 6: 110 << 3(11)에다가 뒤에 0을 붙이면 된다.

솔루션 공부 후 추가로 푼 풀이

#DP + Least Significant Bit
class Solution {
    public int[] countBits(int num) {
        int[] box = new int[num+1];
        box[0]=0;

        for (int i=1; i<=num; i++) {
            box[i] = box[i >> 1] + (i & 1);
        }

        return box;
    }
}

누적되는 알고리즘 접근 설명서

2021/01/09 - [알고리즘 풀이] - .leetcode(알고리즘 문제풀이 접근)