1. 오늘의 문제

Counting Bits

• 출처 : leetcode

2. 문제 분석

• 정수형 변수 : n
• 배열 : ans
• ans의 길이 : n + 1
• ans의 요소 : 2진수로 표현했을 때의 1의 개수

• Example 1
  • Input: n = 2
  • Output: [0, 1, 1]
  • Explanation: 0 ⇾ 0, 1 ⇾ 1, 2 ⇾ 10 (1의 개수 : 1)
• Example 2
  • Input: n = 5
  • Output: [0,1,1,2,1,2]
  • Explanation: 0 ⇾ 0, 1 ⇾ 1, 2 ⇾ 10, 3 ⇾ 11, 4 ⇾ 100, 5 ⇾ 101

3. 문제 풀이

1. n+1 길이의 배열 ans 생성
2. for 문을 0부터 n+1 직전까지 돌아야 함
3. count 변수를 사용해서 2진수에서 1의 개수를 찾아야 함
4. toBinaryString() 메소드 활용해서 2진수로 바꿈
5. 2진수를 돌면서 1의 개수가 있는 만큼 count 변수 증가
6. count 변수를 ans에 넣음

4. 구현 코드

class Solution {
    public int[] countBits(int n) {
        // n+1 길이의 배열 ans 생성
        int[] ans = new int[n+1];

        // for 문을 0부터 n+1 직전까지 돌아야 함
        for (int i = 0; i < n+1; i++) {
            // count 변수를 사용해서 2진수에서 1의 개수를 찾아야 함
            int count = 0;
            // toBinaryString() 메소드 활용해서 2진수로 바꿈
            String binary = Integer.toBinaryString(i);

            // 2진수를 돌면서 1의 개수가 있는 만큼 count 변수 증가
            for (char ch : binary.toCharArray()) {
                if (ch == '1') {
                    count++;
                }
            }
            // count 변수를 ans에 넣음
            ans[i] = count;
        }
        return ans;
    }
}

• 더 빠른 방법

class Solution {
    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의 개수 계산
  • i >> 1 : i를 오른쪽으로 1비트 이동 (2로 나누기). e.g., i = 5(101)일때 i >> 1 은 2(10)임 ⇾ 1의 개수 1 ⇾ 1
  • i & 1 : 1과 AND 비트 연산. e.g., i = 5(101)일 때 i & 1 은 001 (1)임 ⇾ 1의 개수 1 ⇾ 1
  • 따라서 1+1이 result[5]에 들어감

5. 오늘의 회고

• 오늘은 2진수로 변하는 메소드에 대해 배움
• Integer.toBinaryString(int x)
  • 정수형 변수 x를 2진수로 바꿔주는 메소드임
    

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL