[NeetCode-LeetCode] Counting Bits JAVA

반응형

728x90

[NeetCode-LeetCode] Counting Bits - Easy

---

접근

• 비트 연산

---

풀이

0부터 정수 n까지의 모든 숫자에 1이 몇 개 포함되어 있는가 구하는 문제이다.  n = 5 라면 0, 1, 2,..., 3, 4, 5 각 숫자의 1 개수를 배열에 담아 반환하면 된다. 이전 Number of 1 Bits와 같이 비트 조작 유형에 속하는 문제로 비트 연산자를 사용해야 하는 문제인 것 같다. 

 

비트 조작 문제도 맞지만 dp를 사용해야 하는 문제이다. dp를 사용하지 않아도 풀 수는 있어서 난이도가 easy인지 모르겠는데 dp와 비트 조작을 같이 써서 풀면 easy라 하기엔 조금 난이도가 있지 않나? 싶다.

    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;
    }

코드 자체는 간단하다. dp를 사용해 이전 값에 더하면 되는데 여기서 오른쪽 시프트 연산과 and 연산이 사용된다. 오른쪽 시프트 연산은 나누기 2를 하는 것과 동일하지만 문제 이해를 더 쉽게 하기 위해선 오른쪽 시프트 연산으로 보는 게 편하다. 

i = 11 = 1011

오른쪽 시프트 연산 수행
1011 >> 1 = 0101 = 5
시프트 연산 수행 시 5가 가진 1의 개수 + 맨 오른쪽 자릿 값 (i & 1) 동일

이렇게 오른쪽 시프트 연산을 수행하는 경우 나누기 2를 한 숫자의 1의 개수에 기존 맨 오른쪽 자릿 값을 더해주면 총 1의 개수가 구해지기 때문에 dp를 이용해 이전 값에 접근하고 현재 숫자에선 마지막 자리 처리만 해주면 끝이 나게 된다.

---

전체 코드

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;
    }
}