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

문제

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

---

입출력 예

x	y	n	result
10	40	5	2
10	40	30	1
2	5	4	-1

내 풀이

def xToy(x, y, n):
    answer = 0
    while (1):
        x += n
        answer += 1
        if x >= y: break
        while(1):
            if x >= y: break
            x *=3
            answer+=1
        if x >= y: break
        while((y-x) % 2 == 0):
            if x >= y: break
            x *=2
            answer+=1
        if x >= y: break
    
    if y < x: 
        answer = -1
    return answer

def yTOx(x, y, n):
    answer = 0
    while(y % 3 == 0):
        if y == x : break
        y /=3
        answer+=1
        
    while (y % 2 == 0):
        if y == x : break
        y /=2
        answer+=1
        
    while (y > x):
        y -= n
        answer+=1
    if y < x: 
        answer = -1
    return answer

def solution(x, y, n):
    i = xToy(x, y, n)
    j = yTOx(x, y, n)

    if i == -1:
        return j
    elif j == -1:
        return i
    else:
        return min(i, j)

무식한 풀이...

from collections import deque

def solution(start, y, n):
    visit = [-1 for _ in range(1000001)]
    visit[start] = 0
    queue = deque()
    queue.append(start)

    while queue:
        x = queue.popleft()
        if x == y:
            return visit[x]
        for i in (x + n, x * 2, x * 3):
            if 1 <= i <= 10 ** 6 and visit[i] == -1:
                visit[i] = visit[x] + 1
                queue.append(i)
    return -1