LeetCode 338. Counting Bits

문제 요약: 숫자(input)가 주어졌을때, 1부터 주어진 숫자까지 각각 2진수로 변환했을때, 각각 1의 갯수를 배열로 반환 하시오.

 

예:

input: 2 -> 정답: [0,1,1]

input: 5 -> 정답: [0,1,1,2,1,2]

 

문제 접근: 단순하게 반복문을 돌면서, 각각의 숫자를 2진수로 변환해서 1의 갯수를 구하면되는데, 구글링중 2진수의 규칙을 쉽게 구현할 수 있을거 같아서, 그 원리를 코드로 구현했다. 더 효율적인 코드들이 있는거 같지만 이해하는데는 이게 제일 쉬운거 같아서 아래와 같이 구현했다.

 

2진수 규칙: 2의 제곱수다음 숫자는 다음 2의 제곱수가 오기 전까지, 현재의 제곱수에 1부터 더하는 규칙을 가지고 있다. 말로 쓰기 어려워서 아래와 같이 보면 이해하기 쉬울?수도 있다.

0 -> 0

1 -> 1

2 -> 10

3 -> 11      (10 + 1)

4 -> 100  

5 -> 101  (100 + 1)

6 -> 110  (100 + 10)

7 -> 111    (100 + 11)

8 -> 1000

9 -> 1001 (1000 + 1)

...

15 -> 1111 (1000 + 111)

16 -> 10000

...

예를 들면 9는 현재가장큰 2의 제곱수 (8) 에서 1을 더하면 되고, 15는 8에서 7을 더하면 된다. 16은 2의 제곱수이므로 다시 처음부터 반복해야한다.

 

구현코드: Java 사용

class Solution {
	public int[] countBits(int num) {
    	if (num == 0) return new int[]{0};
        if (num == 1) return new int[]{0,1};
        // 정답 배열
        int[] answer = new int[num+1];
        // 초기 처리가 귀찮아서 그냥 강제 입력..
        answer[0] = 0;
        answer[1] = 1;
        answer[2] = 1;
        // 현재 가장큰 2의 제곱수 저장 변수 (변수명 만들기 어려워서..)
        int currentMax2num = 2;
        // 루프를 돌면서 정답배열에 값을 채워나간다.
        for (int i = 3; i <= num; i++) {
        	// 현재 i가 2의 제곱수인지 판별
        	if (is2num(i)) {
            	// 2의 제곱수이면 가장 큰 2의 제곱수를 바꿔주고, 
                // 배열에는 무조건1이다. (8 -> 1000, 16 -> 10000...)
            	currentMax2num = i;
                answer[i] = 1;
            } else {
            	// (9 -> 8(currentMax2num) + 1(9-currentMax2num))
                // (15 -> 8(currentMax2num) + 7 (15 - 8))
            	answer[i] = answer[currentMax2num] + answer[i-currentMax2num];
            }
        }
        return answer;
    }
    
    // 주어진 숫자가 2의 제곱수인지 판단하는 메소드.
    // 2로만 나눴을때 나머지가 없으면 2의 제곱수를 코드로 구현한것.
    public boolean is2 (int num) {
    	boolean result = true;
        if (num % 2 ==  1) return false;
        while (num > 1) {
        	int rest = num % 2;
            if (rest == 1) {
            	result = false;
                break;
            }
            num = num / 2;
        }
        return result;
    }
}

 

규칙만 알면 간단한 문제이고, 효율이 더 좋은 코드들이 있는거 같지만 이해하기가 쉽지 않았다. (내기준) 

또한 메소드명 생각을하다가 많은시간을 투자했지만.. 그냥 위와같이 지음..

그리고 answer[i] = answer[currentMax2num] + answer[i-currentMax2num] 

이부분에서 answer[currentMax2num] 을 1로 바꿔도 될듯하다. (해보진않음)