[leetcode] 338. Counting Bits

문제

 

최초 풀이 -> 이진수로 바꿔서 문자열 형태로 가져온 후 반복문으로 문자 요소 중 1의 개수를 세었다.

중간 풀이 -> 이진수로 바꾸는 과정에서 1이 있으면 세었다.

최종 풀이 -> 비트 연산자를 사용하였다.

 

최종 풀이(3ms)

n & 1 -> 이진수의 1의 자리에 1이 있는지 체크

n >> 1 -> 나누기 2, 이진수에서는 오른쪽으로 한칸씩 미는 것

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            result[i] = count(i);
        }
        return result;
    }

    public int count(int n) {
        int result = 0;
        while(n != 0) {
            result += (n & 1);
            n = n >> 1;
        }
        return result;
    }
}

 

 

중간 풀이(8ms)

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            result[i] = count(i);
        }
        return result;
    }

    public int count(int n) {
        int result = 0;
        while(n != 0) {
            int a = n % 2;
            n = n / 2;
            
            if (a == 1) {
                result++;
            }
        }
        return result;
    }
}

 

 

최초 풀이(32ms)

class Solution {
    public int[] countBits(int n) {
        int[] result = new int[n + 1];
        for(int i = 0; i <= n; i++) {
            String temp = makeBits(i);
            result[i] = countOne(temp);
        }
        return result;
    }

    public int countOne(String str) {
        int result = 0;
        for(int i = 0; i < str.length(); i++) {
            char temp = str.charAt(i);
            if (temp == '1') {
                result++;
            }
        }
        return result;
    }

    public String makeBits(int n) {
        StringBuilder sb = new StringBuilder();
        while(n != 0) {
            int a = n % 2;
            n = n / 2;
            sb.append(a);
        }
        // sb.reverse();
        return sb.toString();
    }
}