[99클럽 코테스터디 2기][Python/비기너] 18번째 문제: Counting Bits

오늘의 주제는 동적계획법

[Counting Bits]

문제

입력과 출력

코드

class Solution:
    def countBits(self, n: int) -> List[int]:
        arr=[]
        num=[]
        
        for i in range(n+1):
            cnt=0
            num=list(bin(i))
            cnt=num.count('1')
            arr.append(cnt)

        return arr
        

알고리즘
0부터 n까지의 숫자들을 각각 이진수로 변환해준다.
이진수로 변환한 후 이를 리스트 형식으로 num에 받아준다.
num배열에서 1의 개수를 세어 cnt에 받아주고
arr배열에 이 cnt를 넣고 arr를 반환해준다.

회고

문제는 이해를 했는데, 처음에는 이진수로 변환하는 함수가 있다는 사실을 몰라서 내가 직접 나머지나 몫을 비교해가며 조건문을 작성했다.
위 사진에서 조건을 잘못 잘아준 듯하여 나머지가 1인 수의 조건을 달아주었는데

코드를 2로 나눈 나머지가 0일때 1을 더해주는 것으로 작성했는데 다른 테스트케이스에서 실행된 결과를 보고나서, 6과 같은 짝수이지만 2의 거듭제곱인 수는 아닌 수를 고려하지 않았다는 것을 확인하였다.

도대체 이 부분을 어떻게 하면 해결하기 좋을까 해서
거듭제곱을 나타낼 수 있는 알고리즘을 찾아보다가
아예 파이썬 내장함수에 bin을 사용하면 이진수 형태로 바꿔줄 수 있다는 것을 알고 시도해보았다.

일단 시도하여 성공했지만 런타임이 104ms..

이건 진짜 아니다 싶어서 코드를 수정해보았다.
먼저 1의 개수를 for문말고 내장함수로 세어줄 수 있을 것 같아서 count를 사용했다.

확실히 줄어들긴 했지만,, 아직 부족하다 생각했다.
bin함수가 어떤 형식으로 반환해주는 지를 모르겠어서 확실치는 않았지만 굳이 리스트로 안받고 bin으로 변환하고 바로 세어줄수는 없을까 싶었다.

결과는 맞았다!
count는 리스트뿐만 아니라 문자열에서 바로 세어줄 수도 있는 함수여서
bin(i)

70ms까지 줄일 수 있었다!
이 이상으로 줄일 수 있는 방법은 모르겠어서,,
스터디에서 비기너 문제도 풀어서 올려주시는 분들이 꽤있는데, 다른 분들의 풀이가 올라오면 참고해보려고 한다!