[프로그래머스] 숫자 변환하기 python

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/154538

문제 설명

자연수 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

접근 방법

문제를 풀기 위해서는 3가지 변환법을 이용해 가능한 모든 경로를 탐색해야 할 것으로 보인다. 왜냐하면 더하기와 곱하기 연산이 공존하기 때문에 역산이 불가능해 연산 순서까지 고려하는 완전 탐색 알고리즘을 적용해야 한다. 그런데 완전 탐색이라고 해서 중복되는 연산을 구태여 반복할 필요는 없다. 실제로 이 문제는 반복 연산을 제거해주지 않으면 시간 초과가 발생하도록 설계되어 있다. 따라서 dictionary 자료구조(hashset)를 이용해서 어떤 숫자는 이미 탐색을 끝냈는 지 확인하도록 하자.
참고로 필자는 deque를 사용하지 않고 list를 queue처럼 사용하는 버릇이 있었는데 이 문제를 풀면서 이러한 버릇을 고치게 되었다. 왜냐하면 list와 deque 자료구조는 메커니즘 자체가 달라서 deque.leftpop()은 시간복잡도가 1인데 반해 list.pop(0)의 경우 시간복잡도가 N이라서 훨씬 오래 걸리게 된다.
자세한 설명은 https://wellsw.tistory.com/122 를 참고하자

풀이 코드

from collections import defaultdict, deque

def solution(x, y, n):
    if x == y: return 0
    queue = deque([[x, 0]])
    duplication = defaultdict(lambda: 0)

    while queue:
        x, cnt = queue.popleft()
        cnt += 1
        
        if duplication[x] == 1:
            continue
        else:
            duplication[x] = 1

        if x + n < y:
            queue.append([x + n, cnt])
        elif x + n == y:
            return cnt

        if 2 * x < y:
            queue.append([2 * x, cnt])
        elif 2 * x == y:
            return cnt

        if 3 * x < y:
            queue.append([3 * x, cnt])
        elif 3 * x == y:
            return cnt

    return -1