[LeetCode] 338. Counting Bits

문제

leetcode.com/problems/counting-bits/

Counting Bits - LeetCode

잠깐만

DP입니다

 

코드

22년 2월 16일 작성 코드

class Solution {
    func countBits(_ n: Int) -> [Int] {
        var oneCount: [Int] = Array(repeating: 0, count: n+1)
        if oneCount.count > 1 {
            oneCount[1] = 1
        }
    
        var standardIndex = 1
        var inputIndex = 2
    
        while inputIndex <= n  {
            if inputIndex % 2 == 0 {
                oneCount[inputIndex] = oneCount[standardIndex]
            } else {
                oneCount[inputIndex] = oneCount[standardIndex] + 1
                standardIndex += 1
            }
            inputIndex += 1
        }
        return oneCount
    }
}

 

 

설명

팔로우업에 "Can you do it in linear time O(n)"라고 써있어서, DP 방법도 있다라는것을 알게됐어요.

그래서 DP로 접근했습니다.

 

다음과 같이 무작정 작성해나갔어요. (빨간 선은 자릿수가 변경되는 시점)

뭔가 보이죠?????? 보인다고 말해주세요. 저랑 같이 공부 했잖아요 ㅠㅜ

 

2는 0과, 3은 1과 패턴이 같네요?

 

그럼 다음 패턴을 찾아볼게요

4는 0과, 5는 1과, 6은 2와, 7은 3과 패턴이 같네요????

우연이 아니길 바라면서 한번 더 패턴을 찾아볼게요

사망 플래그가 아니구요;;;;;;;;;

 

문제는 자릿수 변경되는 시점을 어떻게 파악하는가인데.

2의 제곱수마다 자릿수가 변경된다는것을 알 수 있죠?

2의 현재 제곱수와 다음 제곱수 변수를 활용하여 로직을 구현했습니다.

 

----------------------------------------------------------------------------------------

코드

21년 4월 6일 작성 코드

class Solution {
    func countBits(_ num: Int) -> [Int] {
        var values: [Int] = [Int](repeating: 0, count: num + 1)
    
        if num == 0 {
            return values
        }

        var currentTwoSquare = 0
        var nextTwoSquare = 1
        for i in 1...num {
            if i == nextTwoSquare {
                currentTwoSquare = nextTwoSquare
                nextTwoSquare *= 2
            }
            values[i] = values[i - currentTwoSquare] + 1
        }

        return values
    }
}

 

설명

 

쭉 봐보세요. 앞서 설명한 규칙과는 다른 규칙이 존재하니 한번 찾아보시구요.

 

숫자 2, 3은 숫자 1로부터 파생됐습니다. 보이세요?

숫자 1인 비트 "1" 뒤에 0을 붙이면 숫자 2가 되고,

1을 붙이면 숫자 3이 됩니다.

 



그럼 숫자 4, 5는 어떤 숫자로부터 파생됐을까요?

숫자 2로부터 파생됐습니다.

숫자 2의 비트인 "10" 뒤에, 0을 붙이면 숫자 4가 되고,

1을 붙이면 숫자 5가 됩니다.

 

그럼 느낌 오죠??????

 

숫자 3인 비트 뒤에, 0을 붙이면 6이 되고

1을 붙이면 7이 됩니다.

오?????

그럼 숫자 8과 9는 숫자 4로부터 파생되겠네요???????

이런식으로도 규칙이 존재하고, 값을 계산할 수 있습니다.

 

회고

학부생때 C, C++, 자바(?) 언어에 대한 중간, 기말 고사 시험을 손코딩으로 쳤었는데 도움이 많이 됐습니다.

당시에는 무슨 손코딩이야, 그냥 컴터로 풀면 되는데, 귀찮게 무슨 손코딩이야, 언제쩍 시험이야, 라는 부정적인 생각들을 주로 했었는데,

정말 도움이 많이 됩니다.

 

코딩 전, 로직을 곰곰히 생각해볼 수 있고, 직접 디버깅을 통해 로직에 대한 흐름을 파악할 수 있고, 코드 구현에 대한 능력도 많이 늘어요.

손 코딩, 슈도 코드 적극 활용해요