[프로그래머스, 파이썬] 숫자 변환하기

풀이

• 값 비교를 계속 진행해야 하고 몇 번 작업을 했는지 확인해야 하기에
• deque를 활용하여 해결하고자 했으며
• 처음에는 연산을 마친 값이 y보다 작거나 같을 경우만 해서 q에 추가하여 해결하고자 했지만
• 시간초과가 발생하여 어떻게 하면 좋을지 살펴본 결과
• 방문 표시를 하면 되었기에 해쉬로 값을 찾는 집합 형태로 visit를 만들어 
• 연산 값이 지난 번에 작업하지 않은 값의 경우만 q에 추가하도록 하여 해결.

 

 

from collections import deque

def solution(x, y, n):

    if x == y: return 0

    visit = {x}

    q = deque([[x+n,1],[x*2,1],[x*3,1]])

    while q:

        val,cnt = q.popleft()

        if val == y: return cnt

        for i in [val+n,val*2,val*3]:

            if y >= i and i not in visit:

                visit.add(i)

                q.append([i,cnt+1])

    return -1