[Level 2] 숫자 변환하기(Python)

프로그래머스

문제

자연수 x를 y로 변환하려고 한다. 사용할 수 있는 연산은 다음의 3개가 가능하다.

- x에 n을 더한다.

- x에 2를 곱한다.

- x에 3을 곱한다.

x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return, 만들 수 없다면 -1 return

 

<제한 사항>

- 1 ≤ x ≤ 1,000,000

- 1 ≤ n < y

 

풀이 과정

풀이 시간: 15분

알고리즘: BFS

x와 y를 노드라고 생각한다면 시작 노드에서 도착 노드까지 가는 최단 거리(시간)를 구하는 문제이기 때문에 BFS로 풀이가 가능하다.

 

<시간 복잡도>

O(y): 최악의 경우 y개의 모든 노드를 방문해야 할 수 있기 때문에

from collections import deque


def solution(x: int, y: int, n: int) -> int:
    """
    :param x: 1 이상 1,000,000 이하의 정수
    :param y: 1 이상 1,000,000 이하의 정수
    :param n: 1 이상 y 미만의 정수
    :return: x를 y로 변환하기 위해 필요한 최소 연산 횟수
    """
    if x == y: # x와 y의 값이 같다면 연산 필요없음
        return 0

    queue = deque([(x, 0)])
    visited = set()
    visited.add(x)

    while queue:
        current, steps = queue.popleft() # 현재 좌표, 연산 횟수

        for next_step in (current + n, current * 2, current * 3): # +n, *2, *3을 다음 스텝으로 확인
            if next_step == y:
                return steps + 1
            if 1 <= next_step <= y and next_step not in visited:
                visited.add(next_step)
                queue.append((next_step, steps + 1))

    return -1

 

각 숫자를 일직선에 있다고 생각하면 백준에 거의 유사한 문제인 숨바꼭질이 있다.

다이나믹 프로그래밍으로도 풀이가 가능하지만, 메모리나 실행시간 측면에서 BFS 풀이가 더 빠르다.