프로그래머스 점프와 순간 이동

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

프로그래머스

 

처음에 BFS 풀었다가 효율성에서 막혔다 

from collections import deque

def solution(n):
    q= deque()
    visited = [0 for _ in range(n+1)]
    q.append((1,1))
    visited[1] =1
    
    while q :
        x,step = q.popleft()
        
        if x == n :
            return step
        
        
        for i in [2*x , x +1] :
            if 0<= i <= n and visited[i]:
                continue
            
            elif 0<= i <= n and  not visited[i] and i == 2*x:
                q.append((2*x,step))
                visited[2*x] =1
          
            elif  0<= i <= n  and not visited[i] and i == x+1:
                q.append((x+1,step+1))
                visited[x+1] =1

 

정확도, 효율성 모두 통과한 코드

 

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

    return ans