[LeetCode] - 338. Counting Bits

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Counting Bits" 문제입니다.

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

 

문제 : 

Given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n),

ans[i] is the number of 1's in the binary representation of i.

---

Example 1 :

Input : n = 2

Output : [0,1,1]

Explanation : 0 --> 0 1 --> 1 2 --> 10

 

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

 

Constraints : 0 <= n <= 105

 

Follow up :

It is very easy to come up with a solution with a runtime of O(n log n).

Can you do it in linear time O(n) and possibly in a single pass?

Can you do it without using any built-in function (i.e., like __builtin_popcount in C++)?

---

이 문제는 정수 n에 대해 0부터 n까지의 각 정수에 대해 2진수 표현에서 1의 개수를 세는 배열을 반환하는 것입니다.

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

    public static int countOne(int n) {
        int cntOne = 0;
        for (int i = 0; i < Integer.SIZE; i++) {
            if (((n >> i) & 1) == 1) {
                cntOne++;
            }
        }
        return cntOne;
    }
}

 

이 코드는 주어진 정수 n에 대해 0부터 n까지의 모든 숫자의 2진수 표현에서 '1'의 개수를 구하는 기능을 수행합니다. 각 숫자의 '1'의 개수는 배열에 저장되어 반환됩니다.

코드 구조 및 작동 원리

1. 배열 초기화 :
   • int[] count = new int[n + 1]; : 길이 n+1의 배열을 생성하여 각 인덱스에 해당하는 숫자의 '1'의 개수를 저장합니다.
   • count[0] = 0; : 0의 2진수 표현은 0이며, '1'의 개수는 0입니다.
2. 반복문을 통한 각 숫자의 '1' 개수 계산 :
   • for (int i = 1; i <= n; i++) : 1부터 n까지의 각 숫자에 대해 반복합니다.
   • count[i] = countOne(i); : 각 숫자 i에 대해 countOne 메서드를 호출하여 '1'의 개수를 계산하고 배열에 저장합니다.
3. countOne 메소드 :
   • public static int countOne(int n) : 주어진 정수 n의 2진수 표현에서 '1'의 개수를 계산하는 메서드입니다.
   • int cntOne = 0; : '1'의 개수를 저장할 변수를 초기화합니다.
   • for (int i = 0; i < Integer.SIZE; i++) : 정수 n의 모든 비트를 검사합니다. Integer.SIZE는 자바에서 정수의 비트 수(보통 32비트)를 나타냅니다.
     • ((n >> i) & 1) == 1 : n을 i만큼 오른쪽으로 시프트 하여 가장 오른쪽 비트가 '1'인지 확인합니다.
     • cntOne++ : '1'이면 cntOne을 증가시킵니다.
   • return cntOne; : 최종적으로 '1'의 개수를 반환합니다.
4. 결과 반환 :
   • 계산된 각 숫자의 '1' 개수가 저장된 배열 count를 반환합니다.

시간 복잡도

• countBits 메서드 :
  • O(n * k): n까지의 각 숫자에 대해 countOne을 호출하므로, n개의 숫자를 처리합니다.
  • countOne 메서드는 정수의 모든 비트(32비트)를 검사하므로 O(k)의 시간 복잡도를 가집니다. 여기서 k는 자바 정수의 비트 수입니다.
  • 전체적으로 O(n * 32) ≈ O(n)의 시간 복잡도를 가집니다.

공간 복잡도

• O(n) : 길이 n+1의 배열을 생성하므로, 배열의 크기만큼 공간이 필요합니다.

이렇게 코드를 써봤는데, Submit 누르니까 결과는 생각과는 달리 조금 비효율적이게 나왔습니다. 

 

솔직히 이거보다 어떻게 더 낫게 쓰지 싶어서 고민해봤는데, 시간 복잡도 면에서 O(32 * n) 말고도 O(n) 할만한 게 떠올라서 바로 개선시켰습니다.

---

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

 

DP (동적 프로그래밍)을 써봤는데, 아주 잘 작동합니다. 그리고 이 접근 방식이 문제가 원하는 풀이방식이라고 생각듭니다. 

개선된 접근 설명 :

• count[i] = count[i >> 1] + (i & 1);는 i를 2로 나눈 몫(i >> 1)의 '1'의 개수에 현재 비트의 마지막 자리(i & 1)를 더하는 방식입니다.
• 이는 이전 계산 결과를 활용하여 더 빠르게 1의 개수를 계산합니다.

정리

• 현재 코드 : 모든 비트를 검사하여 각 숫자의 '1' 개수를 계산. O(n * 32) 시간 복잡도.
• 개선된 코드 : 이전 결과를 활용하여 더 빠르게 계산. O(n) 시간 복잡도.

이 개선된 방법은 비트 연산을 사용하여 각 숫자에 대해 빠르게 '1'의 개수를 계산하여 전체적인 효율성을 높입니다.

---

개선 되기 전 후 코드 Runtime 결과