[Leetcode] 338. Counting Bits

Identifying the Problem

0부터 n까지 2진수로 바꾼 결과 1이 각각 1이 몇 개 있는지 배열로 리턴한다.

 

Organizing thoughts

338. Counting Bits

뭐 어떻게 풀지 감이 안잡혀서 엑셀에 써놓고 보니깐 규칙이 보였다.

4 ~ 5은 2칸 앞의 값과 같고,

6 ~ 7은 2칸 앞의 값에 +1 한 값과 같다.

 

8 ~ 11은 4칸 앞의 값과 같고,

12 ~ 15은 4칸 앞의 값에 +1 한 값과 같다.

 

그러면 

16 ~ 16+8-1 은 8칸 앞의 값과 같고,

16+8 ~ 16+8+8-1 은 앞의 값에 +1 한 값과 같다.

 

슬슬 규칙이 보인다.

1. 4 이후부터

2. 해당 값이 간격 칸 앞과 같다가

3. 간격 칸만큼 반복이 진행된 후

4. 해당 값이 간격 칸 앞에 1을 더한 값과 같아진다.

5. 이후 간격 칸수는 2배씩 증가한다.

Sourcecode

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

/*


*/

int* countBits(int n, int* returnSize)
{

    int* ans = malloc(sizeof(int) * (n+1)); //정답 배열
    *returnSize = n+1;
    int two = 2; //간격 칸
    int two_count = 0; //처음 간격 칸
    int next_count = 0; // 이후 간격 칸
    
    for(int i=0;i<=n;i++)
    {
        if(i == 0) ans[i] = 0; //1. (0,1,2,3 은 pass)
        else if(i == 1) ans[i] = 1;
        else if(i == 2) ans[i] = 1;
        else if(i == 3) ans[i] = 2;
        
        else //4이상의 경우
        {
            if(two != two_count) 
            {   two_count++;
                ans[i] = ans[i-two]; //2
            }
            
            else  //3
            {
                ans[i] = ans[i-two] + 1; //4
                next_count++;
            }
            
            if(next_count == two) {two*=2; two_count=0; next_count=0; } //5
            
        }
        
    }
     
    return ans;
}

Mistake

0부터 n까지 해야하는걸 반복문에 습관적으로 0 <n으로 적었다.

New things learned

엑셀 나이스