[막대]

윤호는 64 cm 길이의 막대를 가지고 있지만 x cm만큼 긴 막대가 있다면 더 재밌을 것이라 생각한다. 그는 원래 막대를 작은 막대 여러개로 부수고 풀로 붙여서 정확히 x cm만큼 긴 막대를 만들기로 결심했다.

막대를 부수는 가장 쉬운 방법은 반으로 쪼개는 것이라서 윤호는 다음의 방법을 따르기로 했다:

모든 막대들의 길이를 더한다 (처음에는 64 cm 길이의 막대 하나만 있었다). 길이의 합이 x보다 크다면 다음을 반복한다:

가장 짧은 길이의 막대를 반으로 부순다.

만약 두개 중 하나를 버려도 남아있는 막대들의 길이의 합이 x보다 크다면 하나를 버린다.

마지막으로 남아있는 막대들을 풀로 붙여 x cm길이의 막대를 만든다.

윤호가 위의 단계를 따라하여 풀로 붙이게 될 마지막에 남은 막대들의 개수를 반환하여라. 만약 마지막 단계에서 막대가 하나밖에 없다면 1을 반환하라 (예제 1을 참고하여라).

풀이 1) - python

class Solution:
    def solution(self, x): #2진법의 1의 개수
        return str(bin(x)).count('1')

풀이 2) - python

class Solution:
    def solution(self, x):
        return bin(x)[2:].zfill(6).count("1")

풀이 3) - java

public class Solution{
    public int solution(int x){
        int stickSize = 0;
        for (int stick=64; stick>=1; stick>>=1) {
            stickSize += x / stick;
            x %= stick;
        }
        return stickSize;
    }
}