LeeCode -338 Counting Bits

알고리즘 분류 : DP

예를 들어 2라는 숫자가 주어지면 0부터 2까지의 숫자를 이진수로 바꾸면 0, 1, 10 이 된다. 각각의 이진수의 1의 개수를 배열로 만들면 되는 문제이다.

처음에 생각할 때는 먼저 2까지의 숫자를 이진수로 바꾼 배열을 만든다음 각각의 배열의 요소에서 1의 개수를 찾자는 전략으로 문제를 풀었다. 먼저 주어진 n을 2로 나눈 나머지를 따로 변수로 가지고 있고 몫의 값은 이전 dp에 저장한 값을 사용해 두 변수를 문자열로 더해주면 이진수를 구할 수 있다.

var countBits = function(n) {
    const dp=[]; // 이진수를 만들어줄 배열
    if(n === 0) return [0];
    dp[0]=0;
    dp[1]=1;
    for(let i =2; i<=n; i++){
        const remain = i % 2;
        const quoat  = Math.floor(i/2);
        dp[i]=dp[quoat]+String(remain);
        
    }
     const result = dp.map(item=>{
         let count =0;
         for(let i=0; i<item.length; i++){
           if(item[i] === "1") count++; 
        }
        return count;
     });
    return result;
};

** 개선 코드
다시 생각해보니 굳이 이진수를 만들어준 배열을 만들어준 다음 다시 O(n^2)이나 되는 이중 for 문을 돌려줄 필요가 없다는 걸 깨닫고 코드를 고쳤다.

var countBits = function(n) {
    const dp=[];   
    if(n === 0) return [0];
    dp[0]=0;
    dp[1]=1;
    for(let i =2; i<=n; i++){
        const remain = i % 2;
        const quoat  = Math.floor(i/2);
        dp[i]=dp[quoat]+remain;
        
    }
    return dp;
};

dp에 바로 1의 개수를 저장해준다음 정답을 구하였다.