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

---

문제설명

자연수 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가 될때까지 연산을 하는 방식으로 BFS(Breadth-First Search)방법과 DP(Dynamic Programming) 방법 두 가지로 풀어 낼 수 있다. 완전 탐색을 위하여 그리고 보다 쉽게 구현 할 수 있는 BFS로 접근하여 풀어어보았다. 접근 방식을 큐를 만들어주고 해당 큐에 x를 시작으로 가능한 모든 경우의 수를 y가 되거나 큐가 비는 조건에 탈출하는 반복문을 작성하였다. 풀이 결과 테스트9번과 10번에서 보기좋게 시간초과가 발생하였다.
• 동적계획법으로 다시 풀어야 하나 고민하던 찰나 다른 사람들의 풀이를 잠깐 참고하니 만들어진 숫자를 set에 보관하여 그 숫자에 대해서는 추가 계산을 하지 않도록 하여 경우의 수를 줄인 좋은 아이디어를 알게되었다. y를 만드는 최소의 경우의 수 이기 때문에 추가적으로 방문되는 수는 결국 최소횟수가 아니기 때문이다!
• 반복문을 통과하는 조건을 추가하였더니 정답률 100%를 얻을 수 있었다.

코드 & 설명

from collections import deque

def solution(x, y, n):
    queue = deque()
    queue.append((x,0))
    checker = set()
    
    while queue:
        dx, count = queue.popleft()
        if dx > y or dx in checker:
            continue
        checker.add(dx)
        if dx == y:
            return count
        for i in (dx*3, dx*2, dx+n):
            if i <= y and i not in checker:
                queue.append((i,count+1))
    return -1