(Leetcode) 338 - Counting Bits

New Year Gift - Curated List of Top 75 LeetCode Questions to Save Your Time

위 링크에 있는 추천 문제들을 시간이 있을때마다 풀어보려고 한다.

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

내가 작성한 풀이

public class Solution {
    public int[] countBits(int n) {
        int[] answer = new int[n + 1];
        for (int i = 0; i <= n; i ++) {
            int count = 0;
            String binaryString = Integer.toBinaryString(i);
            for(char binary : binaryString.toCharArray()){
                if(binary == '1') count++;
            }
            answer[i] = count;
        }
        return answer;
    }
}

binary string을 charArray로 변환한 후, ‘1’의 갯수를 카운트 해서 해결하였다.

더 좋은 풀이 방법

public int[] countBits(int n) {
    int result[] = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        int num = i;
        int count = 0;
        while (num > 0) {
            count += num & 1;
            num = num >> 1;
        }
        result[i] = count;
    }
    return result;
}

num 이 0 보다 클경우 shift를 이용하여 1인지 확인하고 1일 경우 count를 1씩 추가한다.

TC, SC

두 풀이의 시간 복잡도는 O(n * log n)이고, 공간 복잡도는 O(n)이다. n * log n 인 이유는 bit의 수는 log 를 따르게 되기 때문이다.

dp로 풀어보기

public int[] countBits(int n) {
    int result[] = new int[n + 1];
    for (int i = 1; i <= n; i++) {
        result[i] = result[i >> 1] + (i & 1);
    }
    return result;
}

1씩 증가함에 따라 비트는 다음과 같이 진행이 된다.

0 = 0000 1 = 0001 2 = 0010 3 = 0011 4 = 0100 5 = 0101 6 = 0110 7 = 0111 …

마지막 bit가 0이 되었다가 1이 되는 것을 반복한다. 이 성질을 이요하면서 이전의 결과값을 이용하면서 마지막 비트의 변화를 관찰한다.

• result[0] = 0
• result[1]
  • result[1 » 1] = result[0] = 0
  • (0001 & 1) = 1
  • 0 + 1 = 1
• result[2]
  • result[2 » 1] = result[1] = 1
  • (0010 & 1) = 0
  • 1 + 0 = 1
• result[3]
  • result[3 » 1] = result[1] = 1
  • (0011 & 1) = 1
  • 1 + 1 = 2
• result[4]
  • result[4 » 1] = result[2] = 1
  • (0100 & 1) = 0
  • 1 + 0 = 1
• result[5]
  • result[5 » 1] = result[2] = 1
  • (0101 & 1) = 1
  • 1 + 1 = 1
• result[6]
  • result[6 » 1] = result[3] = 2
  • (0110 & 1) = 0
  • 2 + 0 = 2
• result[7]
  • result[7 » 1] = result[3] = 2
  • (0111 & 1) = 1
  • 2 + 1 = 3
• …

TC, SC

두 풀이의 시간 복잡도는 O(n)이고, 공간 복잡도는 O(n)이다.