99클럽 코테 스터디 12일차 TIL Counting Bits

Counting Bits

• 문제 풀이

  1. 단순히 2진수로 변환하고 1의 갯수를 구하면 되는 문제였다.

• 풀이 소스

class Solution {
    public int[] countBits(int n) {
        // 2진수
        String binary = "";
        int[] arr = new int[n+1];
        for(int i=0; i<=n; i++){
            binary = Integer.toBinaryString(i); 
            for(int j=0;j<binary.length();j++){
                if(1 == Character.getNumericValue(binary.charAt(j))){
                    arr[i]++;
                }
            }
        }
        return arr;
    }
}

• 시간복잡도 생각한 풀이

class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        int msb = 1;
        for (int i = 1; i <= n; i++) {
            if(i>>1 == msb) msb = i;
            ans[i] = 1 + ans[i-msb];
        }
        
        return ans;
    }
}

• 오늘의 회고

  • 문제 시도 및 해결

    • 2진수로 반환 후 각 해당하는 값에 대해 1을 체크하여 ++를 해주었다.
    • 문제를 풀고나니 제한사항이 보였다.
    • 다른 방법으로 문제를 해결해야 했다.
    • 주어진 조건에서 반복되는 패턴을 찾아야했다.
      
    • 마지막과 같은 반복되는 패턴을 알 수 있었다.

  • 학습 내용 및 회고

    • 문제에 대해서 공부하다가 Integer.bitCount라는 메소드를 알 수 있었다.
    • 눈으로만 이해할려고 하니까 불가능했다.
    • 다른 사람이 풀이 해준 내용을 참고하여 이해할 수 있었다.
    • 이런 유형의 반복되는 패턴을 찾는 연습을 해야겠다.
    • 나누기2보다 비트연산이 더 빠르다는 것을 알았다.

  • 다음 배울것

    • Spring boot 공부
    • 코테 문제 풀이