[프로그래머스] 점프와 순간 이동(Python)

https://programmers.co.kr/learn/courses/30/lessons/12980

코딩테스트 연습 - 점프와 순간 이동

 

Greedy 유형 같긴 하다. 2로 나눠지면 그냥 나누고 안 나눠지면 1을 빼고 정답에는 1씩 더하면 된다.

 

나의 풀이

def solution(n):
    answer = 0
    while n!=0:
        if n%2 ==0:
            n = n//2
        else:
            n -=1
            answer+=1
    return answer

다른 사람 풀이

def solution(n):
    return bin(n).count('1')

처음엔 이해가 안 갔는데,

이진수로 표현했을 때 맨 끝자리가 0이면 2로 나눠지고 1이면 2로 나눠지지 않는 수다.

이진수에서 맨 끝자리가 1일 때 1을 뺄 경우 맨 끝자리는 0이 된다

이진수에서 맨 끝자리가 0일 때 2로 나눌 경우 맨 끝자리의 0은 사라진다.

 

0 0b0
1 0b1
2 0b10
3 0b11
4 0b100
5 0b101
6 0b110
7 0b111
8 0b1000
9 0b1001
10 0b1010

10을 예로 들면,

10은 1010 끝자리가 0이니 2로 나눈다. -> 5인 101로 변환

5는 101 끝자리가 1이니 1을 빼준다. -> 4인 100으로 변환

4는 100 끝자리가 0이니 2로 나눈다. -> 2인 10으로 변환

2는 10 끝자리가 0이니 2로 나눈다. -> 1인 1로 변환

1은 1 끝자리가 1이니 1을 빼준다. -> 0인 0로 변환

 

보면서 눈치챘겠지만, 결국 이진수에서 1만 세주게 되면 원하는 답이 된다.